记录编号	302026	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]子串	最终得分	100
用户昵称	confoo	是否通过	通过
代码语言	C++	运行时间	1.539 s
提交时间	2016-09-03 09:26:40	内存使用	1.31 MiB

#include<cstdio>
#define file(x) "2015substring."#x
const int MAXN=1010,MAXM=210;
typedef long long ll;
const ll M=1000000007;
ll f[2][MAXM][MAXM][2];
int n,m,k;
char A[MAXN],B[MAXM];
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout); 
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s%s",A+1,B+1);
	f[1][0][0][0]=f[0][0][0][0]=1;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=k&&j<=i;j++){
			for(int p=1;p<=m&&p<=i;p++){
				if(A[i]==B[p])
					f[i%2][j][p][1]=f[(i-1)%2][j-1][p-1][0]+(f[(i-1)%2][j][p-1][1]+f[(i-1)%2][j-1][p-1][1]);
				else f[i%2][j][p][1]=0;
				f[i%2][j][p][0]=(f[(i-1)%2][j][p][1]+f[(i-1)%2][j][p][0]);
				f[i%2][j][p][1]%=M;
				f[i%2][j][p][0]%=M;
				//printf("f[%d][%d][%d]:%lld %lld\n",i,j,p,f[i%2][j][p][0],f[i%2][j][p][1]);
			}
		}
	}
	printf("%lld",(f[n%2][k][m][1]+f[n%2][k][m][0])%M);
}