题解 | #D - Double String#

看了看dalao们的解释和代码，于是有了这篇题解

题目大意

给定两个字符串A，B，求出满足以下条件的子序列a,b（可以不连续）的数量，并对 $10^9+7$ 取模：

a，b分别来自A，B，且长度 $length$ 相同
$\exist i \in [1,length]$ ,使得 $a_i < b_i$
$\forall j \in [1, i)$ ,满足 $a_j = b_j$ 。
对于 $k \in [i + 1, length]$ ， $a_k,b_k$ 没有任何限制。

思路

假如我们已经找到了 $A_{a1}...A{a_n}$ ，和 $B_{b_1}...B_{b_n}$ 相同，那么我们只需要在 $A$ 数组 $A_{a_n}$ 后面中找到一个字母 $A_{a_{n+1}}$ ，在 $B$ 数组 $B_{b_n}$ 后面中找到一个字母 $B_{b_{n+1}}$ ，满足 $A_{a_{n+1}} < B_{b_{n+1}}$ 即可，那么剩下的字母就可以随便选了。
假设 $A$ 数组还剩 $n$ 个数可选， $B$ 数组还剩 $m$ 个可选，那么利用组合数学，就可知道共有 $\sum_{i=0}^{min(n,m)} C_n^i + C_m^i$ 种选法。而此式子等于 $C_{n+m}^n$ 。（具体证明可以参照百度）。~~（蒟蒻不太会）~~
那么剩下的就是统计数组有多少个字串是相同的了。我们假设表示在数组前位，数组的前位***有几个相同的字串，递推时(有点类似与最长公共子序列)：
- 如果 $A[i] \not= B[j]$ ，那么它显然是由 $A$ 数组前 $i-1$ 个字母和 $B$ 数组前 $j$ 个组成，或者是 $A$ 数组前 $i$ 个字母和 $B$ 数组前 $j-1$ 个组成的。但是如果我们直接加上 $dp[i-1][j],dp[i][j-1]$ 的话，会出现多加的情况，那就是 $A$ 数组前 $i-1$ 个字母和 $B$ 数组前 $j-1$ 个组成的,所以我们要再减去 $dp[i-1][j-1]$ ，综上： $dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]$ 。
- 如果 $A[i] = B[j]$ ，那么它显然也可以由 $dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]$ 得到一部分结果，其他的部分，就是由 $A$ 数组前 $i-1$ 个字母和 $B$ 数组前 $j-1$ 个，再加上 $A[i],B[j]$ 两个字母，即 $dp[i-1][j-1]$ ，其次 $A[i],B[j]$ 两个字母也可以单独作为结果计算，综上： $dp[i][j]=dp[i-1][j]+dp[i][j-1]+1$ 。
因为结果是要求对结果进行取模的，而且我们的计算中是存在组合数的，所以不能每次都用费马小定理，所以我们需要预处理出阶乘数组和其对应的乘法逆元数组。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

typedef  long long ll;
const int maxN = 2000005, mod = 1000000007;

ll inv[maxN + 1], f[maxN + 1];

string s1, s2;
long long dp[5005][5005];
int len1, len2;

void exgcd(int a, int b, ll &x, ll &y) //拓展欧几里得
{
    if(b == 0) {
        x = 1; y = 0;
        return ;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

void init()
{
    f[0] = 1;
    for(int i = 1; i <= maxN; ++i)
        f[i] = f[i - 1] * i % mod; //阶乘数组
    ll x, y;
    exgcd(f[maxN], mod, x, y);
    inv[maxN] = (x % mod + mod) % mod;
    for(int i = maxN - 1; i; --i) {
        inv[i] = inv[i + 1] * (i + 1) % mod; //逆元数组
    }
}

ll C(ll n, ll m)
{
    if(n == m || m == 0)
        return 1;
    if(m > n)
        return 0;
    return (f[n] * inv[m] % mod * inv[n - m] % mod) % mod;
}

int main()
{
    cin >> s1; cin >> s2;
    len1 = s1.length(); len2 = s2.length();
    s1 = " " + s1; s2 = " " + s2;
    init();
    for(int i = 1; i <= len1; ++i) {
        for(int j = 1; j <= len2; ++j) {
            if(s1[i] == s2[j])
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % mod;
            else
                dp[i][j] = ((dp[i - 1][j] + dp[i][j - 1]) % mod + mod - dp[i - 1][j - 1]) % mod;
        }
    }
    long long ans = 0;
    for(int i = 1; i <= len1; ++i) {
        for(int j = 1; j <= len2; ++j) {
            if(s1[i] < s2[j]) {
                long long n = len1 - i, m = len2 - j;
                ans = (ans + (dp[i - 1][j - 1] + 1ll) * C(1LL * n + m, 1LL * min(n, m)) % mod) % mod;
            }
        }
    }
    cout << ans << endl;
    return 0;
}