思路

事先说明：

n

表示

S

长度，

n_1

和

n_2

分别是

s_1

和

s_2

的长度。

对于每个区间，定义

a_i

表示该区间有多少个子序列是

s_1[1\dots i]

，

b_i

是

s_2[1\dots i]

。这个区间的贡献就是

a_{n_1}\times b_{n_2}

。

假定一个区间的右端点右移了一位，如果新加入的字符在

s_1

中的

x

处出现了，相当于让

a_x

加上了

a_{x-1}

。如果在

s_2

（此处同上，略）。所以我们可以定义一个

f_{i,j,k}

表示所有右端点在

i

的区间的

\sum{a_j\times b_k}

的值，转移因为过于简单，放到代码里。发现这个 DP 式子存储的时候可以把

i

给消掉看着更简洁，所以最终时间复杂度

O(n\times n_1\times n_2)

，空间复杂度

O(n)

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=22,mod=998244353;
int n,n1,n2;
char a[N],s1[M],s2[M];
string s;
int f[M][M],ans;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	//没用的输入部分
	cin>>s;n=s.size();for(int i=1;i<=n;i++)a[i]=s[i-1];
	cin>>s;n1=s.size();for(int i=1;i<=n1;i++)s1[i]=s[i-1];
	cin>>s;n2=s.size();for(int i=1;i<=n2;i++)s2[i]=s[i-1];
	//有用的转移部分
	for(int i=1;i<=n;i++){
		f[0][0]++;//我们认为一个区间只有一个子序列是空串
		for(int j=n1;j>=1;j--){//从大到枚举的原因 同01背包
			if(s1[j]==a[i]){
				for(int k=0;k<=n2;k++)f[j][k]=(f[j][k]+f[j-1][k])%mod;
			}
		}
		for(int k=n2;k>=1;k--){
			if(s2[k]==a[i]){
				for(int j=0;j<=n1;j++)f[j][k]=(f[j][k]+f[j][k-1])%mod;
			}
		}
		ans=(ans+f[n1][n2])%mod;
	}
	cout<<ans<<"\n";
	return 0;
}

题解：P10694 [SNCPC2024] 双子序列

文章操作

思路

代码

相关推荐

评论

题解：P10694 [SNCPC2024] 双子序列