题解：P11655 「FAOI-R5」Lovely 139

· · 题解

题目描述

对于一个 01 串 S（下标从 1 开始），我们定义它的一个区间 [l,r] 是极长颜色段，当且仅当它同时满足以下条件：

定义 g(S) 为 S 的不同极长颜色段数。

定义 f(n,m) 的值为所有恰好包含 n 个 0 和 m 个 1 的 01 串 S 的 g(S) 之和。

回答 T 个问题，每次给出 n,m 的值，求 f(n,m) \bmod (10^9+7) 的值。

样例

输入

3
2 2
4 6
7 8

输出

18
1218
54483

算法

(组合计数、逆元)

易得 g(S)=1+\sum_{i=1}^{n+m-1}[S_i \ne S_{i+1}]。

先考虑 1，由于有 C_{n+m}^n 个 01 串 S，所以一共加了 C_{n+m}^n 个 1。

在 S 中，对于 \forall i \in [1,n+m)，若 S_i \ne S_{i+1}，对答案的贡献为 1。S_i 和 S_{i+1} 有 01 和 10 两种可能，其余的 n+m-2 个数字随便排列，有 C_{n+m-2}^{n-1} 中排列。 所以对于 \forall i，所有 [S_i \ne S_{i+1}] 的和对答案的贡献为 2 \times C_{n+m-2}^{n-1}， 由于一共有 n+m-1 个 i，所以所有 \sum_{i=1}^{n+m-1}[S_i \ne S_{i+1}] 的和对答案的贡献为 2 \times C_{n+m-2}^{n-1} \times (n+m-1)。

综上所述，答案为

C_{n+m}^n+2 \times C_{n+m-2}^{n-1} \times (n+m-1)

预处理 fac 数组存储阶乘，inv 数组存储逆元，facinv 数组存储阶乘的逆元，可得 C_a^b=\frac{a!}{b!(a-b)!}=fac_a \times facinv_b \times facinv_{a-b}。

时间复杂度 O(T)

C++ 代码

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 2000010, MOD = 1e9 + 7;

int fac[N], inv[N], facinv[N];

LL C(int n, int m) { //计算组合数
    return (LL)fac[m] * facinv[m - n] % MOD * facinv[n] % MOD;
}

int main() {
    fac[0] = facinv[0] = inv[1] = 1; //初始化
    for (int i = 1; i < N; i++) //计算阶乘数组
        fac[i] = (LL)fac[i - 1] * i % MOD;
    for (int i = 2; i < N; i++) //计算逆元数组
        inv[i] = MOD - (LL)inv[MOD % i] * (MOD / i) % MOD;
    for (int i = 1; i < N; i++) //计算阶乘的逆元数组
        facinv[i] = (LL)facinv[i - 1] * (LL)inv[i] % MOD; //逆元的地推公式
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        int ans = 0;
        if (!n || !m) { //特判
            puts("1");
            continue;
        }
        //计算答案
        ans = (2ll * (n + m - 1) * C(n - 1, m + n - 2) % MOD + C(n, n + m)) % MOD;
        printf("%d\n", ans);
    }
    return 0;
}