自动搬运

查看原文

来自洛谷，原作者为

	LiWenX 4587

搬运于2025-08-24 23:00:20，当前版本为作者最后更新于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;
}