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$；
• $?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;
}