- \(70pts\) ：
记 \(sub_A(i)\) 表示 \(A\) 的前 \(i\) 个字符构成的子串，相应地，\(sub_B(i)\) 为 \(B\) 的前 \(i\) 个字符构成的子串。
设 \(f(i, j, k)\) 表示在 \(sub_A(i)\) 中选出 \(k\) 个互不相交的子串，且按照它们在 \(sub_A(i)\) 中出现的顺序首尾相连后与 \(sub_B(i)\) 相同的方案数。
设 \(p \in \N\)，满足 \(\forall l \in [0, p - 1], A_{i - l} = B_{j - l} \and A_{i - p} \ne B_{j - p}\)。
\[f(i, j, k) = f(i - 1, j, k) + \sum_{l = 1}^p f(i - l, j - l, k - 1) \]时间复杂度 \(O(nmk)\)，但空间复杂度 \(O(nmk)\)，会 MLE。
- \(100pts\)：
消去 \(i\) 这一维后，就不能随时计算 \(\sum\limits_{l = 1}^p f(i - l, j - l, k - 1)\) 了，所以令 \(s(j, k) = \sum\limits_{l = 1}^p f(i - l, j - l, k - 1)\)，每次先更新 \(s(j, k)\)，再根据 \(s(j, k)\) 更新 \(f(j, k)\) 即可。
\[s(j, k) = \left\{ \begin{aligned} s(j - 1, k) + f(j - 1, k)&, A_i = B_j \\ 0&, A_i \ne B_j \end{aligned} \right. \]代码：
#include <bits/stdc++.h>
#define MAXN 1100
#define MAXM 210
#define MOD 1000000007
using namespace std;
int n, m, p, K, f[MAXM][MAXM], s[MAXM][MAXM];
char A[MAXN], B[MAXM];
int main() {
scanf("%d%d%d%s%s", &n, &m, &K, A + 1, B + 1);
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = m; j; j--) {
for (int k = K; k; k--) {
if (A[i] == B[j]) s[j][k] = (f[j - 1][k - 1] + s[j - 1][k]) % MOD;
else s[j][k] = 0;
f[j][k] = (f[j][k] + s[j][k]) % MOD;
}
}
}
printf("%d", f[m][K]);
return 0;
}