题解：P11655 「FAOI-R5」Lovely 139

· · 题解

我们需要计算所有恰好包含 n 个 0 和 m 个 1 的 01 串的极长颜色段数之和，并对结果取模 10^9 + 7。极长颜色段是指一个区间内所有字符相同且无法扩展的区间。

极长颜色段数计算：

1.对于一个 01 串，极长颜色段数等于相邻不同字符对的数量加 1。

例如，0011 的极长颜色段数为 2，0101 的极长颜色段数为 4。

2.组合数学： 所有恰好包含 n 个 0 和 m 个 1 的 01 串的数目为组合数 C(n + m, n)。

对于每个字符串，极长颜色段数等于相邻不同字符对的数量加 1。

3.相邻不同字符对的总数： 每个相邻位置对的贡献为 2 种方向（0 后接 1 或 1 后接 0）。

总共有 (n + m - 1) 个相邻对，总贡献为 2 * (n + m - 1) * C(n + m - 2, n - 1)。

4.预处理阶乘和逆元： 预处理阶乘数组和逆元数组，快速计算组合数。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;          
const int MAX = 2e6 + 10;         

long long e[MAX], g[MAX];        

// 快速幂函数：计算a^b mod mod
long long f(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和阶乘的逆元
void ff() {
    e[0] = 1; // 0的阶乘为1
    // 计算阶乘数组 e[i] = i! mod MOD
    for (int i = 1; i < MAX; ++i) {
        e[i] = e[i - 1] * i % MOD;
    }
    // 计算MAX-1位置的逆元，即 (MAX-1)! 的逆元
    g[MAX - 1] = f(e[MAX - 1], MOD - 2, MOD);
    // 递推计算逆元数组 g[i] = (i! 的逆元)
    for (int i = MAX - 2; i >= 0; --i) {
        g[i] = g[i + 1] * (i + 1) % MOD;
    }
}

// 计算组合数C(a, b)
long long C(int a, int b) {
    if (a < 0 || b < 0 || b > a) return 0; 
    return e[a] * g[b] % MOD * g[a - b] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ff(); 

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        // 处理特殊情况：n=0且m=0时答案为1（题目要求）
        if (n == 0 && m == 0) {
            cout << "1\n";
            continue;
        }
        long long t = C(n + m, n);
        long long s = 0;
        // 当n和m均不为0时，计算相邻不同对的总数
        if (n > 0 && m > 0) {
            int a = n + m - 2;
            int k = n - 1;
            //选择n-1个0放在剩下位置的方案数
            long long c = C(a, k);
            // 每个相邻位置对的贡献为2种方向（0后接1或1后接0）
            // 总共有(n+m-1)个相邻对，总贡献为2*(n+m-1)*C(n+m-2, n-1)
            s = (1LL * (n + m - 1) * 2) % MOD;
            s = s * c % MOD;
        }
        // 答案 = 所有字符串的极长颜色段数之和 = 相邻不同对数总和 + 字符串数目
        long long ans = (t + s) % MOD;
        cout << ans << '\n';
    }
    return 0;
}