Double Strings

2021-08-13

字数统计: 979字 | 阅读时长≈ 4分

题目大意

给定两个字符串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,B\)数组有多少个字串是相同的了。我们假设\(dp[i][j]\)表示在\(A\)数组前\(i\)位，\(B\)数组的前\(j\)位中共有几个相同的字串，递推时(有点类似与最长公共子序列)：
- 如果\(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;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/08/13/Double-Strings/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！