次元传送门：洛谷P2679
思路
蒟蒻一开始并没有思路而去看了题解
我们发现对于两个字串的位置 我们只需要管他们匹配成功或者匹配失败即可
f[i][j][k] 记录当前 a[i]不论等不等于b[j] 我们可以选用也可以不选用 使用k个子串方案数（因为题目没有要求一定位置相同）
r[i][j][k] 记录当前 a[i]==b[j] 并且我们选用a[i]和b[j] 方案数 使用k个子串方案数
状态转移方程：
if(A[i]==B[j])
r[i][j][k]=(f[i-][j-][k-]+r[i-][j-][k])%mod;
//f[i-1][j-1][k-1] 我们把当前匹配字符单独算做一个子串
//r[i-1][j-1][k] 我们把当前匹配字符与前面的串合并为一个子串 else r[i][j][k]=;
//不成则为零 f[i][j][k]=(r[i][j][k]+f[i-][j][k])%mod;
//r[i][j][k] 使用当前字符
//f[i-1][j][k] 不使用当前字符
因为数组并开不了辣么大
所以我们要用到滚动数组
把第一维该为0和1循环使用即可
代码
#include<iostream>
#include<cstring>
using namespace std;
#define mod 1000000007
int n,m,K,now;
char a[],b[];
int f[][][],r[][][];
int main()
{
cin>>n>>m>>K;
cin>>a+>>b+;
f[][][]=;
now=;//滚动下标
for(int i=;i<=n;i++)
{
f[now][][]=;
for(int j=;j<=m;j++)
for(int k=;k<=K;k++)
{
if(a[i]==b[j])
r[now][j][k]=(r[now^][j-][k]+f[now^][j-][k-])%mod;
else
r[now][j][k]=;
f[now][j][k]=(f[now^][j][k]+r[now][j][k])%mod;
}
now^=;
}
cout<<f[now^][m][K];
}