1. 题目

传送门=￣ω￣=

2. 题解

首先不难想到：
设 $f[i][j][k]$为第一个字符串的前 i 个字符和第二个字符串的前 j 个字符匹配，用了 k 个子串时的方案数。
那么 $f[i][j][k]=f[i-1][j-1][k]+f[i-1][j-1][k-1]$，$f[i-1][j-1][k]$表示不新建一个子串，$f[i-1][j-1][k-1]$表示新建一个子串
然而我们发现，这样处理第 i 个字符必然会被选择，也就是我们少处理了很多状态。
那么我们分情况讨论。
新建一维，状态变为 4 维，第 4 维为 0 或 1，表示第 i 个字符选或者不选。
则：
1. 第 i 个字符不选：那上一个状态要么选择了第 i-1 个字符，要么没选择第 i-1 个字符。
2. 第 i 个字符要选：那上一个状态要么没选择第 i-1 个字符，那现在必须新建一个子串；要么选择了第 i-1 个字符，可以新建子串，也可以不新建。这种情况需要满足第 i 个字符和第 j 个字符相同

所以状态转移方程：
$$f[i][j][l][0]=f[i-1][j][l][0]+f[i-1][j][l][1]$$
$$f[i][j][l][1]=f[i-1][j-1][l-1][0]+f[i-1][j-1][l-1][1]+f[i-1][j-1][l][1]$$

另：注意开 long long

代码：

#include <bits/stdc++.h>
#define MOD (1000000007ll)
using namespace std;
typedef long long LL;
LL n,m,k,f[2][205][205][2],cnt;
char s1[1005],s2[205];
int main()
{
    scanf("%lld%lld%lld%s%s",&n,&m,&k,s1+1,s2+1);
    for(LL i=1;i<=n;i++)
    {
        f[i&1][1][1][0]=cnt;
        if(s1[i]==s2[1])f[i&1][1][1][1]=1,cnt++;
        for(LL j=2;j<=m;j++)
            for(LL l=1;l<=k;l++)
            {
                f[i&1][j][l][0]=(f[(i&1)^1][j][l][0]+f[(i&1)^1][j][l][1])%MOD;
                if(s1[i]==s2[j])
                    f[i&1][j][l][1]=
                        (f[(i&1)^1][j-1][l][1]
                        +f[(i&1)^1][j-1][l-1][0]
                        +f[(i&1)^1][j-1][l-1][1])%MOD;
            }
        for(LL j=1;j<=m;j++)
            for(LL l=1;l<=k;l++)
                f[(i&1)^1][j][l][0]=f[(i&1)^1][j][l][1]=0;
    }
    printf("%lld\n",(f[n&1][m][k][0]+f[n&1][m][k][1])%MOD);
    return 0;
}