题目大意：
给定两个长度分别为 n 和 m 的字符串 A 和 B，选取 A 中的 k 个子串，使这 k 个子串按照先后顺序连接起来后等于 B 子串。
输入输出样例
输入 #16 3 1aabaabaab输出 #12 输入 #26 3 2 abaab aab输出 #27 输入 #36 6 3aabaabaab输出 #37
首先，看题目的要求。对于这类题目要求，以及如此之小的数据范围，考虑使用动态规划。
/*————————加一段解释一下为什么要设0 / 1这一维—————————————*/
首先定义状态f[i][j][k]代表A里前i个字符挑出k个子串组成b的前j个字符的总方案数，那答案就是f[n][m][k]；
然后想怎么转移
1.a[i] == b[j]
f[i][j][k] = f[i-1][j-1][k-1] + f[i-1][j-1][k] + f[i-1][j][k]
考虑a[i]可以自己一个人组成子串，跟前面的A[i-1]相连组成子串和不选A[i]
2.a[i] != b[j]
f[i][j][k] = f[i-1][j][k] （那就是不选A[i]）
但是，实际上， 在第一种情况中，dp[i-1][j-1][k]这样的表达是错误的。
因为这种情况要求A[i-1]必须被选中，但f[i-1][j-1][k]指的是从A的前i-1个字符中挑出k个子串组成B的前j-1个字符，并没有规定一定要选A[i-1]。所以想到要再
多加一个状态0/1表示选不选A[i]
设计状态（需要记录什么？）：
1、A串匹配到哪里
2、B串匹配到哪里
3、当前已经用了多少子配串（k）
4、上一位和这一位选还是不选（会影响到k，于是必须记录）
于是，设计状态 f[i][j][p][0/1]， 来表示A串匹配到 i 位， B串匹配到 j 位， 已经使用了 p 个子串，这一位选/不选的最大方案数。
然后想状态方程：
如果啊 a[i] == b[j]
那么有 f[i][j][p][0] = f[i – 1][j][p][0] + f[i – 1][j][p][1] ; （即为上一位选和不选之和）
f[i][j][k][1] = f[i-1][j-1][k][1]（跟上一个连成一串） + f[i-1][j-1][k-1][1]（小团体，上一个用） + f[i-1][j-1][k-1][0]（小团体，上一个不用）
如果不相等，
不选的情况和上面一样： f[i][j][p][0] = f[i – 1][j][p][0] + f[i – 1][j][p][1] ;
对于选择的情况，两个不一样，肯定不能选 所以 f[i][j][p][1] = 0;
如此开数组，内存有点吃不消。（起码比赛的时候不敢开到8 * 107）的int数组。
观察一下状态方程，发现我们的 i 这一维， 永远都是i – 1, 也就是说，之前用过的有很大程度上是浪费的。
于是我们用 ^ 操作让这一维滚动起来。
千少万少，代码不能少
#include <bits/stdc++.h>
#define N 1010
#define M 210
#define isdigit(c) ((c)>='0'&&(c)<='9')
const int mod = (int)(1e9)+;
using namespace std;int f[][M][M][];
char a[N],b[M];
int n, m, k;
bool flag = ;inline int read(){
int x = , s = ;
char c = getchar();
while(!isdigit(c)){
if(c == '-') s = -;
c = getchar();
}
while(isdigit(c)){
x = (x << ) + (x << ) + (c ^ '');
c = getchar();
}
return x * s;
}int main(){
n = read(), m = read(), k = read();
scanf("%s%s",a + , b + ); /*一定要从第一位开始，而不能从0开始，不然之后会造成数组越界*/
f[][][][] = f[][][][] = ;
for(int i = ;i <= n; i++, flag ^= ){
for(int j = ;j <= m; j++){
for(int p = ;p <= k; p++){
if(a[i] == b[j]){
f[flag][j][p][] = (f[flag^][j][p][] % mod + f[flag^][j][p][] % mod) % mod;
f[flag][j][p][] = (f[flag^][j-][p][] % mod + (f[flag^][j-][p-][] + f[flag^][j-][p-][]) % mod) % mod;
}
else{
f[flag][j][p][] = ((f[flag^][j][p][] + f[flag^][j][p][]) % mod);
f[flag][j][p][] = ;
}
}
}
}
printf("%d\n",(f[n&][m][k][] + f[n&][m][k][]) % mod);/*用n的奇偶来判断滚动维度最后是 1 还是 0*/
return ;
}
