洛谷题面

题目大意

给出两个长度分别为 \(N\) 和 \(M\) 的整数序列 \(\rm S\) 和 \(\rm T\)，它们均由 \(1\) 到 \(10^{5}\) (含) 之间的整数组成。

求在 \(\rm S\) 子序列和 \(\rm T\) 子序列中，有多少对两个子序列的内容相同。

子序列的说明:

\(\rm A\) 的子序列是指通过从 \(\rm A\) 删除零个或多个元素而不改变顺序而获得的序列。

对于 \(\rm S\) 和 \(\rm T\) 而言，如果子序列的内容相同，但是被删除元素的索引集(位置)不同，也当成两个不同的子序列。

输出答案 \(\operatorname{mod}1e9+7\) 的结果。

题目分析

令 \(dp[i][j]\) 表示在 \(\rm S\) 的前 \(i\) 项和 \(\rm T\) 的前 \(j\) 项中有多少对相同的公共子序列。

分析一波：

\(dp[i][j]\) 当然是由 \(dp[i-1][j]\)、\(dp[i][j-1]\) 和 \(dp[i-1][j-1]\) 更新来的。

如果当前进行匹配的两个数字不相同的话，前两个显然会出现重合，于是接下来套路了，套一下容斥原理即可。

用 \(S[i]\) 表示 \(\rm S\) 的第 \(i\) 位，\(T[i]\) 表示 \(\rm T\) 的第 \(i\) 位。

当 \(S[i]\not=T[j]\) 时，有

\[dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] \]

否则有

\[dp[i][j]=dp[i-1][j]+d[i][j-1] \]

然后需要注意一下取模会出现负数和初始化即可。

代码

//2021/9/8

//2021/9/9

#include <iostream>

#include <cstdio>

#include <string>

#define debug(c) cerr<<#c<<" = "<<c<<endl

using namespace std;

const int ma=2005;

const int mod=1e9+7;

int s[ma],t[ma];

long long dp[ma][ma];

int n,m;

int main(void)
{
	cin.tie(nullptr),cout.tie(nullptr);
	
	cin>>n>>m;
	
	dp[0][0]=1ll;//初始化
	
	for(register int i=1;i<=n;i++)
	{
		cin>>s[i];
		
		dp[i][0]=1ll;//初始化
	}
	
	for(register int i=1;i<=m;i++)
	{
		cin>>t[i];
		
		dp[0][i]=1ll;//初始化
	}
	
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=m;j++)
		{
			if(s[i]!=t[j])
			{
			    dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%mod;
			}
			
			else
			{
			    dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
			}
		}
	}
	
	cout<<(dp[n][m]%mod+mod)%mod<<endl;
	
	return 0;
}