组合数前缀和以及相关恒等式

https://blog.csdn.net/caoyang1123/article/details/119682449

https://blog.nowcoder.net/n/81842ed1c5a14330902d3ef9a7403c6f

const int N = 5007;
const int mod = 1e9 + 7;
int fac[N * 2] = {1, 1}, inv[N * 2] = {1, 1};
inline void init() {
    for (int i = 2; i < N * 2; ++i) {
        fac[i] = (ll)fac[i - 1] * i % mod;
        inv[i] = (ll)(mod - mod / i) % mod * inv[mod % i] % mod;
    }
    for (int i = 1; i < N * 2; ++i) inv[i] = (ll)inv[i] * inv[i - 1] % mod;
}
inline int C(int n, int m) {
    if (n < m) return 0;
    if (n == m) return 1;
    return (ll)fac[n] * inv[m] % mod * inv[n - m] % mod;
}

ll C(ll n, ll m) {//组合数 C(n,m)
    if (m < 0) return 0;
    if (n < m) return 0;
    if (m > n - m) m = n - m;
    ll up = 1, down = 1;
    for (ll i = 0; i < m; i++) {
        up = up * (n - i) % mod;
        down = down * (i + 1) % mod;
    }
    return up * getInv(down) % mod;
}

Double Strings

用dp转移相同子序列数量，用组合数计算两串选出等长串，能选多少种

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 5007;
const int mod = 1e9 + 7;
int fac[N * 2] = {1, 1}, inv[N * 2] = {1, 1};
int dp[N][N];  // dp[i][j]表示 在A串前i个字符 B串前j个字符 有多少子序列相同
char a[N], b[N];
inline void init() {
    for (int i = 2; i < N * 2; ++i) {
        fac[i] = (ll)fac[i - 1] * i % mod;
        inv[i] = (ll)(mod - mod / i) % mod * inv[mod % i] % mod;
    }
    for (int i = 1; i < N * 2; ++i) inv[i] = (ll)inv[i] * inv[i - 1] % mod;
}
inline int C(int n, int m) {
    if (n < m) return 0;
    if (n == m) return 1;
    return (ll)fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main() {
    init();
    scanf("%s%s", a + 1, b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);
    rep(i, 1, n) rep(j, 1, m) {
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod;
        // 考虑不在两串中同时加入本字符的情况，那么就要么从a串尾缀，要么从b串尾缀，容斥处理一下即可
        if (a[i] == b[j]) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + 1) % mod;
        // 如果a[i] == b[j] 即考虑同时在两串中加入本字符的情况
        // dp[i][j]可以自dp[i-1][j-1]转移（即尾缀本字符）
        // 也可以重新开始（+1） 即从本位开始
        if (dp[i][j] < 0) dp[i][j] += mod;
    }
    ll ans = 0;
    rep(i, 1, n) rep(j, 1, m) 
        if (b[j] > a[i]) 
            // 前面相同（加一个空串），后面随便选
            ans = (ans + (ll)(dp[i - 1][j - 1] + 1) * C(n - i + m - j, n - i)) % mod;
    pr(ans);
    return 0;
}