记录编号	449361	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]子串	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.515 s
提交时间	2017-09-14 08:55:30	内存使用	1.28 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,m,k,f[3][205][205];
char a[1005],b[205];
int main()
{
	freopen("2015substring.in","r",stdin);
	freopen("2015substring.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%lld%lld%lld",&n,&m,&k);
	scanf("%s%s",a+1,b+1);
	for(ll i=0;i<=2;i++)
	f[i][0][0]=1;
	for(ll p=1;p<=n;p++){
		for(ll j=1;j<=min(p,m);j++){
			for(ll o=1;o<=min(k,j);o++){
				ll i=p%3;
				f[i][j][o]=f[(i-1+3)%3][j][o];
				if(a[p]==b[j]){//如果当前为相同，则独自成一个串 
					f[i][j][o]+=f[(i-1+3)%3][j-1][o-1];
					f[i][j][o]%=mod;
					if(a[p-1]==b[j-1]&&p>=2){//如果上一位也相同，那么加上所有上一位被选并且串数等于当前串数的情况 
						ll an=(f[(i-1+3)%3][j-1][o]-f[(i-2+3)%3][j-1][o]+mod)%mod;
						f[i][j][o]+=an;
					}
				}
				f[i][j][o]%=mod;
			}
		}
	}
	cout<<f[n%3][m][k]%mod;
	return 0;
}