题解：P10694 [SNCPC2024] 双子序列

BuQiuRu4587 · 2024-07-09 09:02:49 · 题解

看完题，感觉这个子序列有点难直接做的，至少直接算出每一个区间的贡献估计是没有前途，所以我们考虑拆贡献。

乘法形式拆贡献有经典 trick，使用乘法分配律，发现对于一对子序列 l_1,l_2，设他们第一个出现位置最小值是 L，最后一个出现位置最大值为 R，这对子序列贡献为 L(n-R+1)。那么答案改写为 \sum\limits_{l_1,l_2}L(n-R+1)。

这个形式已经足够 dp 了，具体来说，我们考虑枚举 R，dp 计算 \sum L 的值，然后可以设出状态 f_{i,j,k} 表示考虑到了 s 的第 i 位，匹配到了 s1 的第 j 位，s2 的第 k 位，左端点的和。那么答案就是 \sum\limits_{i=1}^nf_{i,|s1|,|s2|}(n-i+1)。

考虑转移，这是相当简单的，f_{i,j,k}=\sum\limits_{p=1}^{i-1}([s1_j=s_i]f_{p,j-1,k})+([s2_k=s_if_{p,j,k-1}])+([s1_j=s_i \land s2_k=s_i]f_{p,j-1,k-1}) 特判这是左端点再加上 i 即可。

使用前缀和优化可以做到 O(|s||s1||s2|)。

最开始答案没取模罚了一发/fn。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
string s,s1,s2;
int f[100005][21][21];
int sum[21][21];
int n,l1,l2;
void rtt(int x){
    for(int i=0;i<=l1;i++){
        for(int j=0;j<=l2;j++){
            sum[i][j]+=f[x][i][j];
            if(sum[i][j]>=mod) sum[i][j]-=mod; 
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>s>>s1>>s2;
    n=s.size(),l1=s1.size(),l2=s2.size();
    s='#'+s;
    s1='#'+s1;
    s2='#'+s2;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=l1;j++){
            for(int k=0;k<=l2;k++){
                if(s1[j]!=s[i]&&s2[k]!=s[i]) continue;
                if(s1[j]==s[i]){
                    f[i][j][k]+=sum[j-1][k]+(j==1&&k==0)*i;
                    if(f[i][j][k]>=mod) f[i][j][k]-=mod;
                }
                if(s2[k]==s[i]){
                    f[i][j][k]+=sum[j][k-1]+(j==0&&k==1)*i;
                    if(f[i][j][k]>=mod) f[i][j][k]-=mod;
                }
                if(s1[j]==s[i]&&s2[k]==s[i]){
                    f[i][j][k]+=sum[j-1][k-1]+(j==1&&k==1)*i;
                    if(f[i][j][k]>=mod) f[i][j][k]-=mod;
                }
            }
        }
        ans+=f[i][l1][l2]*(n-i+1)%mod;
        rtt(i);
    }
    cout<<ans%mod;
}