题目大意

给你两个字符串，长度在级别，询问在两者的全部子序列中，长度相等，并且的数量有多少个？

Solution

考点：相同子序列数量

如果直接考虑，因为子序列并不知道第几个位置不同，所以这个并不好处理，但是我们一定可以把这个的子序列分成段。

第一段：子序列前个字符都相同。

第二段：

第三段：剩余长度任意挑选子序列。

先考虑如何求解任意两个位置相同子序列数量，这个用动态规划处理。

我们用代表以前个字符，前个字符的相同子序列数量，那么我们可以写出下面的转移方程。

当的时候减掉的是重复计算的，当的时候加上的是一定选他们结尾的时候前面相同的，加上前面一个不选。

好了我们已经预处理出了数组了，下面就要考虑后面长度任选怎么处理。

如果我们枚举到串后面还剩长度为，串后面长度为，那么等价与求

上面这个式子可以做个等价变换，首先我们知道，那么就变成了我有两堆球，我要在左边拿出个球，右边拿出个球的方案数总和，并且提供这个乘法之后求合我们可以判断这些球都是完全不一样的，那不就等价于我一共有个球，要拿出个球的方案数吗，所以我们得到

接下来就只要计算答案就行了，总的时间复杂度是。

const int N = 5e3 + 7;
ll n, m;
int f[N][N];

ll jc[N << 1], inv[N << 1];
void init() {
    jc[0] = 1;
    for (int i = 1; i < N * 2; ++i)    jc[i] = jc[i - 1] * i % MOD;
    inv[N * 2 - 1] = qpow(jc[N * 2 - 1], MOD - 2, MOD);
    for (int i = N * 2 - 2; ~i; --i)    inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m) {
    return jc[n] * inv[m] % MOD * inv[n - m] % MOD;
}

char s[N], t[N];

int solve() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i] == t[j]) {
                f[i][j] = (f[i - 1][j] + f[i][j - 1] + 1) % MOD;
            }
            else {
                f[i][j] = ((f[i - 1][j] + f[i][j - 1]) % MOD - f[i - 1][j - 1] + MOD) % MOD;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i] < t[j]) {
                res = (res + (f[i - 1][j - 1] + 1) * C(n - i + m - j, n - i) % MOD) % MOD;
            }
        }
    }
    print(res);

    return 1;
}