【牛客竞赛】Double String题解

题目大意

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

• a，b分别来自A，B，且长度 $length$ 相同
• $\exists\ i \in [1, length]$
• $\forall\ j \in [1, i),\ a_j = b_j$
• 对于 $k \in [i+1, length]$，$a_k < b_k$（即第 $i$ 位之后 a 严格小于 b）

题目链接

思路

• 假如我们已经找到了 $A_{a_1}\ldots A_{a_n}$（来自A的子序列）和 $B_{b_1}\ldots B_{b_n}$（来自B的子序列），且它们前 $n$ 位相同，那么我们需要从 $A_{a_{n+1}}$ 和 $B_{b_{n+1}}$ 开始，满足 $A_{a_{n+1}} < B_{b_{n+1}}$。

• 假设 A 数组还剩 $n$ 个数可选，B 数组还剩 $m$ 个可选，那么利用组合数学，可知共有 $C_{n+m}^n$ 种方式分别从 $A, B$ 选出相同数量的字符。

• 那么如何知道 $A, B$ 数组有多少个子串是相同的呢？我们假设 $dp[i][j]$ 表示在 A 数组前 $i$ 位，B 数组前 $j$ 位中共有几个相同的子串，递推时（有点类似于最长公共子序列）：

  • 如果 $A[i] \ne 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]$：可由上述公式得到一部分结果，其他部分是由 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;
}