题解：P10694 [SNCPC2024] 双子序列

elswzl · 2025-04-21 23:36:53 · 题解

思路

事先说明：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)。

代码

#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;
}