Description
我们可以换个思路。
从字符串 \(A\) 中拿出 \(k\) 个字串使其变成 \(B\)。求有几种不同的方案？
Analysis
我们发现 \(A\) 中的一个字符取或者不取影响后面的决策，这并不代表它一定有后效性，我们可以记录这一层状态。
和最长公共子序列同理，定义 \(f_{i,j,k,l}(\forall l \in \{1,0\})\) 表示前 \(i\) 位 \(A\)，前 \(j\) 位 \(B\)，共用 \(k\)个字串，\(A_i\) 选或者不选时的方案数。
每次开始讨论前初始化令 \(f_{i,j,k,0}=f_{i,j,k,1}=0\)。因为接下来都是更新操作。
接下来开始分类讨论。
- 首先所有情况\(A_i\) 都可以不选，不管是否 \(A_i = B_j\) 。我们这样枚举的目的是尽可能一一对应。所以 \(f_{i,j,k,0}=f_{i-1,j,k,0}+f_{i-1,j,k,1}\)
Explanation：\(A_i\) 不能选，则 \(B\) 不改变。显然 \(A_{i-1}\) 选或者不选都可以推到到这一步。所以等于他俩方案数的和。
- 当 \(A_i = B_j\) ，这种情况我们可以选择 \(A_i\)。则满足 \(f_{i,j,k,1}=f_{i-1,j-1,k,1}+f_{i-1,j-1,k-1,0}+f_{i-1,j-1,k,0}+f_{i-1,j-1,k-1,1}\)。
Explanation：显然这一位属于公共子串。我们可以把它和上一位归到一个字串内，也可以单独另开一个字串。这都是算作不同的方案数。选或不选也都是不同的方案数。
同时，我们这是四维数组，肯定MLE。容易发现 \(A_i\) 只和 \(A_{i-1}\) 有关系，所以我们显然可以压缩掉第一维状态。
具体实现见代码：
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 300;
const int mod = 1000000007;
int n,m,K;
char s1[3000],s2[N];
int f[N][N][N][3];
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
scanf("%d%d%d",&n,&m,&K);
scanf("%s",s1+1);
scanf("%s",s2+1);
f[0][0][0][0] = 1;
for(int i=1;i<=n;i++)
{
int op = i & 1;
f[op][0][0][0] = 1;
for(int j=1;j<=min(i,m);j++)
{
for(int k=1;k<=min(j,K);k++)
{
f[op][j][k][0] = f[op][j][k][1] = 0;
f[op][j][k][0] = (f[op^1][j][k][0]+f[op^1][j][k][1]) %mod;
if(s1[i] == s2[j])
{
f[op][j][k][1] = (f[op^1][j-1][k][1]+f[op^1][j-1][k-1][0]) % mod;
(f[op][j][k][1] += f[op^1][j-1][k-1][1]) %= mod;
}
}
}
}
printf("%d\n",(f[n&1][m][K][1]+f[n&1][m][K][0])%mod);
}