Description：

专业挖坑不填 100 年

Solution：

设 \(f_{i,j,k,1/0}\) 表示 \(A_{1..i} , B_{1..j}\) 且子串数为 \(k\) 的方案数。

则：当 \(a_i=b_j\) 时：

$$$$

（先留坑。。。

Code：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4;
const int M = 1e3;
const int mod = 1e9+7;
int n,m,K;
int f[M][M][2];
char a[N],b[N];

int main()
{
    scanf("%d%d%d\n",&n,&m,&K);
    gets(a+1);gets(b+1);
    f[0][0][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=min(i,m);j>=1;--j)
        {
            for(int k=1;k<=min(j,K);++k)
            {
                if(a[i]==b[j])
                {
                    f[j][k][0]=(f[j][k][0]+f[j][k][1])%mod;
                    f[j][k][1]=((f[j-1][k-1][0]+f[j-1][k-1][1])%mod+f[j-1][k][1])%mod;//这里 % 一次导致调了1h-，真·细节决定成败。。。 
                }
                else if(a[i]!=b[j])
                {
                    f[j][k][0]=(f[j][k][0]+f[j][k][1])%mod;
                    f[j][k][1]=0;
                }
            }
        }
    }
    printf("%d\n",(f[m][K][0]+f[m][K][1])%mod);
    return 0;
}