记录编号	212991	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]子串	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.525 s
提交时间	2015-12-09 08:42:41	内存使用	1.64 MiB

#include<cstdio>

#define maxn 1010
#define maxm 210
#define MOD 1000000007

using namespace std;

int n,m,K;
long long f[2][maxm][maxm][2];

char s1[maxn],s2[maxn];

int main()
{
	freopen("2015substring.in","r",stdin);
	freopen("2015substring.out","w",stdout);
	scanf("%d%d%d", &n, &m, &K);
	scanf("%s%s", s1+1, s2+1);
	f[0][0][0][0]=1;
	for(int i = 1; i <= n; i++){
		int tmp=i&1;
		for(int j = 0;j <= m && j<=i; j++){
			for(int k = 0 ; k <= K; k++){
				f[tmp][j][k][1]=f[tmp][j][k][0]=0;
				if(s1[i] == s2[j] && k>0 && j>0) 
					(f[tmp][j][k][1] = f[tmp^1][j-1][k][1] + f[tmp^1][j-1][k-1][0] +f[tmp^1][j-1][k-1][1])%=MOD;
				(f[tmp][j][k][0] = f[tmp^1][j][k][1] + f[tmp^1][j][k][0])%=MOD;
			}
		}	
	}
	printf("%lld",(f[n&1][m][K][0] + f[n&1][m][K][1])%MOD);
	return 0;
}