自动搬运

查看原文

来自洛谷，原作者为

	littleKtian MoVe yoUR BoDy

搬运于2025-08-24 22:23:09，当前版本为作者最后更新于2020-07-18 07:59:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

以下题解内容由

记$f[i][j]$表示在$A$的前$i$个与$B$的前$j$个中有多少相同的子序列（包含空串）

$g[i][j]$表示在$A$的后$i$个与$B$的后$j$个中有多少相同的子序列（同上）

考虑$A$中的区间$[i,k]$在所有分割串的方案中出现的次数。

那就需要在$A$中的子序列$P$跨过$[i,k]$这个区间，必须要有$i-1$和$k+1$这两个位置，且其他的位置在$[1,i-2]$或$[k+2,n]$之间。

枚举在$B$中与$P$匹配的子序列$Q$，设$P$的$i-1$这个位置与$Q$在$j$匹配，

那就有式子$f[i-2][j-1]\times(g[k+1][j+1]-g[k+2][j+1])$，且$A[i-1]=B[j]$。

故在$A$中总答案就是$\sum\limits^{n}_ {i=1} \sum\limits^{n}_ {k=i} \sum\limits^{m+1}_ {A[i-1]=B[j]}f[i-2][j-1]\times(g[k+1][j+1]-g[k+2][j+1])\times(k-i+1)^t$

时间复杂度$O(n^3)$。

设$j$是固定的，构造多项式$G[x]=g[x+1][j+1]-g[x+2][j+1]$， $V[x]=x^t$

原式变为$\sum\limits^{m+1}_ {j=0}\sum\limits_ {A[i-1]=B[j]} f[i-2][j-1] \sum\limits^{n}_ {k=i} G[k]\times V[k-i+1]$

只要把$G$翻转然后用$NTT$把$G$和$V$做卷积，对于每个$i$取卷积后的第$n-i+1$项系数即可。

时间复杂度$O(n^2logn)$。应该不卡常吧，std开O2跑500ms

（std中枚举的是区间$[i+1,k]$，会有所不同）

#include<bits/stdc++.h>
#define N 1010
#define MOD 998244353
#define ll long long
using namespace std;
int n,m,t,ans;
int a[N<<2],v[N<<2],f[N][N],g[N][N];
//v[i]=i^t
//f[i][j]表示前(i,j)里相同子序列的方案数
//g[i][j]表示后(i,j)里相同子序列的方案数
char s1[N],s2[N];
//视s1[0]=s2[0],s1[n+1]=s2[m+1]
int rev[N<<2];
int len,bit;
//ntt用 
inline int ksm(int x,int k)
{
	int res=1;
	while(k)
	{
		if(k&1)res=1ll*res*x%MOD;
		x=1ll*x*x%MOD;
		k>>=1; 
	}
	return res;
}
inline int qm(ll x)
{
	return (x%MOD+MOD)%MOD;
}
inline void ntt(int len,int a[],int inv)
{
	for(int i=1;i<len;i++)
		if(i<rev[i])
			swap(a[i],a[rev[i]]);
	for(int i=1;i<len;i<<=1)
	{
		int gi,up=i<<1;
		if(inv==1)gi=ksm(3ll,(MOD-1)/up);
		else gi=ksm(1ll*(MOD+1)/3,(MOD-1)/up);
		for(int j=0;j<len;j+=up)
		{
			int gx=1;
			for(int k=0;k<i;k++)
			{
				int x=a[j+k],y=1ll*gx*a[i+j+k]%MOD;
				a[j+k]=qm(x+y),a[i+j+k]=qm(x-y);
				gx=1ll*gx*gi%MOD;
			}
		}
	}
	if(inv==-1)
	{
		int invx=ksm(len,MOD-2);
		for(int i=0;i<len;i++)
			a[i]=1ll*a[i]*invx%MOD;
	}
}
inline void getmul(int lenx,int a[])
{
	ntt(len,a,1);
	for(int i=0;i<len;i++)
		a[i]=1ll*a[i]*v[i]%MOD;
	ntt(len,a,-1);
	for(int i=lenx;i<len;i++)
		a[i]=0;
}
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	scanf("%s",s1);
	scanf("%s",s2);
	for(int i=n;i>=1;i--)s1[i]=s1[i-1];
	for(int i=m;i>=1;i--)s2[i]=s2[i-1];
	for(int i=max(n,m);i>=1;i--)
		v[i]=ksm(i,t);
	len=1,bit=-1;
	while(len<2*max(n,m)+1)len<<=1,++bit;
	for(int i=1;i<len;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<bit);
	ntt(len,v,1);//因为都是与V做卷积，直接预处理 ,当然不这样也能过
	s1[0]=s2[0]=' ';
	for(int i=0;i<=n;i++)f[i][0]=1;
	for(int i=0;i<=m;i++)f[0][i]=1;
	for(int i=1;i<=n+1;i++)g[i][m+1]=1;
	for(int i=1;i<=m+1;i++)g[n+1][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			f[i][j]=qm(f[i-1][j]+f[i][j-1]-f[i-1][j-1]);
			if(s1[i]==s2[j])
				f[i][j]=qm(f[i][j]+f[i-1][j-1]);
		}
	for(int i=n;i>=1;i--)
		for(int j=m;j>=1;j--)
		{
			g[i][j]=qm(g[i+1][j]+g[i][j+1]-g[i+1][j+1]);
			if(s1[i]==s2[j])
				g[i][j]=qm(g[i][j]+g[i+1][j+1]);
		}
	//计算A中答案 
	for(int j=1;j<=m;j++)
	{
		a[n]=0;
		for(int k=1;k<=n;k++)
			a[n-k]=qm(g[k+1][j+1]-g[k+2][j+1]);//构造多项式 
		getmul(n,a);//计算卷积 
		for(int i=1;i<=n;i++)
			if(s1[i]==s2[j])//此处枚举的是区间[i+1,k] 
				ans=qm(ans+1ll*a[n-i]*f[i-1][j-1]%MOD);
	}
	for(int i=1;i<=n;i++)a[i]=0;
	//计算B中答案 
	for(int i=1;i<=n;i++)
	{
		a[m]=0;
		for(int k=1;k<=m;k++)
			a[m-k]=qm(g[i+1][k+1]-g[i+1][k+2]);
		getmul(m,a);
		for(int j=1;j<=m;j++)
			if(s1[i]==s2[j])
				ans=qm(ans+1ll*a[m-j]*f[i-1][j-1]%MOD);
	}
	for(int i=max(n,m);i>=1;i--)
		v[i]=ksm(i,t);
	for(int k=1;k<=n;k++)
		ans=qm(ans+1ll*qm(1ll*qm(g[k+1][1]-g[k+2][1])*v[k]%MOD));//f[-1][j-1]特殊处理 
	for(int k=1;k<=m;k++)
		ans=qm(ans+1ll*qm(1ll*qm(g[1][k+1]-g[1][k+2])*v[k]%MOD));
	printf("%d",ans);
}