原题
\(题目大意\)
\(从字符串a中选出k个子串s_1,s_2,s_3...s_k使得s_1+s_2+s_3+...+s_k=b\)
\(求总方案数对10^9+7取模的结果\)
\(1\le |a|即n\le 1000,1 \le |b|即m\le 200,1\le k\le |b|\)
\(设f_{i,j,x}表示已经选到a的第i个字符，b的第j个字符，共选了x个子串的方案数\)
\(则可得转移式f_{i,j,x}=f_{i-1,j,x}\sum_{a[l,i]=b[r,j]}f_{l-1,r-1,x-1}\)
\(a[l,i]=b[r,j]意为a的l到i区间与b的r到j区间相等\)
\(但是如果这样转移，复杂度为O(nmk\cdot n\cdot m^2)，显然过不了，考虑优化\)
\(观察可以发现，对于a[l,i]=b[r,j]的l,r枚举其实可以进行预处理\)
\(把a和b看作两条链\)
\(如样例aabaab和aab\)
\(即为\)
\(对于每组i,j,l,r，因为要求相等，所以i-l和j-r是相等的\)
\(可以由l向r连一条边，记录i-l的值\)
\(于是变成这样\)
\(理论上来说，这样最多跑出nm^2条边，但是因为在每一层x的枚举中，每条边都至多使用一次，所以复杂度降到了O(nm^2k+nm^2)\)
\(据这题的数据O约为1000*200^3=8,000,000,000=8*10^9\)
\(但是实际上这个复杂度很难跑满，在加上常数小，于是可以过?\)
\(但是观察f_{i,j,x}的状态，发现大小为nm^2=1000*200^2=4*10^7\)
\(显然MLE\)
\(但是看到转移式f_{i,j,x}=f_{i-1,j,x}\sum_{a[l,i]=b[r,j]}f_{l-1,r-1,x-1}\)
\(f_{i,j,x}的转移只用到了f_{l,r,x-1}\)
\(所以可以把第3维滚动掉\)
\(变成f_{l,r,0/1}，空间为2nm=4*10^5\)
\(于是便愉快的AC了\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct zi
{
short l,r;
int lt;
}d[4000009];
int head[1009];
int top;
void mkb(int x,short l,short r)
{
top++;
d[top].l=l;
d[top].r=r;
d[top].lt=head[x];
head[x]=top;
}
const int mod=1e9+7;
short n,m,k;
int f[1002][202][2];
string a,b;
int main()
{
cin>>n>>m>>k;
cin>>a>>b;
for(short i=1;i<=n;i++)
for(short j=1;j<=m;j++)
{
string s1="",s2="";
for(short len=1;i+len-1<=n&&j+len-1<=m;len++)
{
s1+=a[i+len-2];
s2+=b[j+len-2];
if(s1==s2)
mkb(i,j,j+len-1);
else
break;
}
}
for(short i=0;i<=n;i++)
f[i][0][0]=1;
for(short x=1;x<=k;x++)
{
for(short i=0;i<=n;i++)
for(short j=0;j<=m;j++)
f[i][j][x%2]=0;
for(short i=1;i<=n;i++)
{
for(short j=1;j<=m;j++)
f[i][j][x%2]=(f[i][j][x%2]+f[i-1][j][x%2])%mod;
for(int opt=head[i];opt;opt=d[opt].lt)
{
short j=i+d[opt].r-d[opt].l;
f[j][d[opt].r][x%2]=(f[j][d[opt].r][x%2]+f[i-1][d[opt].l-1][(x+1)%2])%mod;
}
}
}
cout<<f[n][m][k%2];
return 0;
}