洛谷P11655「FAOI-R5」Lovely 139

P11655「FAOI-R5」Lovely 139

题目背景

Update：数据有 0 0，答案为 1，请选手特判以正常通过。

$\text{Height}\le 139$。

题目描述

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

• 如果 $l\ne 1$，$S_{l-1}\ne S_l$；
• 如果 $r\ne |S|$，$S_{r+1}\ne S_r$；
• $\forall i\in [l,r),S_i=S_{i+1}$。

定义 $g(S)$ 为 $S$ 的不同极长颜色段数。比如 $g($$00$$)=1$，$g($$1110$$)=2$，$g($$001011$$)=4$。

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

你需要回答 $T$ 个问题，每次给出 $n,m$ 的值，求 $f(n,m)$ 的值对 $10^9+7$ 取模后的结果。

输入格式

第一行输入一个正整数数 $T$，表示问题个数。

接下来 $T$ 行，每行两个非负整数 $n,m$，表示问题的参数。

输出格式

输出 $T$ 行，每行为对应问题的答案。

样例 #1

样例输入 #1

3
2 2
4 6
7 8

样例输出 #1

18
1218
54483

样例 #2

样例输入 #2

3
845 826
672 826
618 925

样例输出 #2

789284214
588160420
730993180

样例 #3

样例输入 #3

1
1 46

样例输出 #3

139

提示

样例 1 解释

对于第一组数据 $n=2,m=2$，一共有六个本质不同的 $S$，答案为 $g($$0011$$)+g($$0101$$)+g($$0110$$)+g($$1001$$)+g($$1010$$)+g($$1100$$)=2+4+3+3+4+2=18$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（15 pts）：$0\le n+m\le 20$，$1\le T\le 10$。
• Subtask 2（25 pts）：$0\le n+m\le 4\times 10^3$。
• Subtask 3（20 pts）：$1\le T\le 10$。
• Subtask 4（40 pts）：无特殊限制。

对于所有数据，保证 $1\le T\le 10^6$，$0\le n+m\le 2\times 10^6$，$0\le n,m\le 2\times 10^6$。

题解思路

问题描述

给定一个包含 $n$ 个 0 和 $m个1的01` 串 $S$，定义 $g(S)$ 为 $S$ 的不同极长颜色段数。极长颜色段 $[l,r]$ 需要满足以下条件：

1. 如果 $l\ne 1$，则 $S_{l-1}\ne S_l$；
2. 如果 $r\ne |S|$，则 $S_{r+1}\ne S_r$；
3. 对于所有 $i\in [l,r)$，$S_i=S_{i+1}$。

定义 $f(n,m)$ 为所有满足条件的 01 串 $S$ 的 $g(S)$ 之和，需要对 $10^9+7$ 取模。

解题思路

1. 计算 $g(S)$ 的贡献

对于任意一个 01 串 $S$，$g(S)$ 可以通过以下方式计算：

• $g(S)$ 等于 $S$ 中满足 $S_i\ne S_{i-1}$ 的位置 $i$ 的数量，再加上 $1$。

2. 贡献分解

将 $f(n,m)$ 的贡献分解为两部分：

1. 基础的贡献：每个 01 串 $S$ 的基础贡献为 $1$，因为 $g(S)$ 至少包含一个极长颜色段。总共有 $\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$ 个 01 串，因此这部分的总贡献为：
   $$\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$$
2. 变化的贡献：对于每个位置 $i$，如果 $S_i\ne S_{i-1}$，则会对 $g(S)$ 产生额外的贡献。对于每个位置 $i$，$S_{i-1}$ 和 $S_i$ 可以是 01 或 10，其余 $|S|-2$ 个位置可以任意排列。因此，每个位置 $i$ 的贡献为：
   $$2\times \left(\genfrac{}{}{0ex}{}{n+m-2}{n-1}\right)$$
   由于总共有 $n+m-1$ 个可能的位置 $i$，因此这部分的总贡献为：
   $$(n+m-1)\times 2\times \left(\genfrac{}{}{0ex}{}{n+m-2}{n-1}\right)$$

3. 总贡献

将两部分贡献相加，得到 $f(n,m)$ 的表达式：
$$f(n,m)=\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)+(n+m-1)\times 2\times \left(\genfrac{}{}{0ex}{}{n+m-2}{n-1}\right)$$

4. 模运算

由于结果需要对 $10^9+7$ 取模，因此在计算组合数时需要使用模运算和预处理阶乘及其逆元来高效计算组合数。

总结

通过将 $f(n,m)$ 的贡献分解为基础贡献和变化贡献，并利用组合数学的知识，可以高效地计算出 $f(n,m)$ 的值。最终的结果需要对 $10^9+7$ 取模，以确保结果的正确性。

代码：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;

const int MAX = 2000000 + 10; // 2e6 + 10
long long fact[MAX], inv_fact[MAX];

long long qpow(long long a, long long b) { // 快速幂
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute() { // 预处理阶乘和阶乘逆元
    fact[0] = 1;
    for (int i = 1; i < MAX; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[MAX - 1] = qpow(fact[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

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

void solve() {
    int n, m;
    cin >> n >> m;
    if (n == 0 || m == 0) {
        printf("1\n");
        return;
    }
    int a = n + m;
    int term1 = (a - 1) * 2 % MOD;
    term1 = term1 * comb(a - 2, n - 1) % MOD;
    int term2 = comb(a, n) % MOD;
    int ans = (term1 + term2) % MOD;
    cout << ans << endl;
}

signed main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    precompute();
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}