记录编号	271387	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]子串	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.813 s
提交时间	2016-06-15 21:34:13	内存使用	1.76 MiB

#include<stdio.h>
#include<stdlib.h>
#define mod 1000000007
long long f[2][1010][210]={0};
int a=0,n,m,i,j,k,l;
char A[1010]={0},B[210]={0};
int _521()
{
	freopen("2015substring.in","r",stdin);
	freopen("2015substring.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s%s",A+1,B+1);
	for(i=0;i<=n;i++) f[0][i][0]=1;
	for(l=1;l<=k;l++)
	{
		a^=1;
		for(i=0;i<=n;i++) f[a][i][l-1]=0;
		for(i=l;i<=m;i++)
		{
			for(j=i;j<=n;j++)
			{
				if(A[j]==B[i])
				{
					f[a][j][i]=f[a^1][j-1][i-1]+f[a][j-1][i-1]+f[a][j-1][i];
					f[a][j][i]%=mod;
					if(j>=2) f[a][j][i]=(mod+f[a][j][i]-f[a][j-2][i-1])%mod;
				}
				else f[a][j][i]=f[a][j-1][i];
			}
		}
	}
	printf("%lld\n",f[a][n][m]);
	return 0;
}
int _520=_521();
int main(){;}