题解：[CodePlus 2018 3 月赛] 博弈论与概率统计

题目难度：NOI/NOI+/CTSC
时间限制：1.00s
内存限制：512MB

题目大意

Alice 和 Bob 进行 $N+M$ 轮游戏。已知 Alice 恰好赢了 $N$ 轮，输了 $M$ 轮。初始分数为 0，赢一轮加 1 分，输一轮扣 1 分。但如果分数为 0 时输掉比赛，则分数不变（对方照常加分）。

求游戏结束时 Alice 得分的数学期望，结果对 $10^9+7$ 取模。

解题思路

1. 问题转化

如果没有“0 分不扣分”的规则，Alice 的最终得分就是 $N - M$。
由于有了“0 分不扣分”的限制，每当 Alice 在 0 分时输掉比赛，她的实际得分会比理论得分 $N-M$ 多 1（因为本该扣分但没扣）。

因此，最终得分 = $N - M +$（在 0 分时输掉的局数）。

我们需要计算在所有 $C_{N+M}^N$ 种胜负序列中，Alice 在 0 分状态输掉比赛的期望次数。

2. 组合计数与分类讨论

设 $S(n, k)$ 表示在 $n$ 轮游戏中，Alice 获胜次数不超过 $k$ 的方案数（即前缀和）。

根据 $N$ 和 $M$ 的大小关系，分两种情况讨论：

• 情况一：$M \le N$ (输的局数少于赢的局数)
  • 此时 $N-M \ge 0$，Alice 的分数很难长时间维持在 0。
  • 期望得分公式推导为：$E = (N-M) + \frac{S(N+M-1, M-1)}{C_{N+M}^N}$。
• 情况二：$M > N$ (输的局数多于赢的局数)
  • 此时 Alice 必定会多次回到 0 分并面临扣分。
  • 期望得分公式推导为：$E = \frac{S(N+M-1, N-1)}{C_{N+M}^N}$。

3. 算法优化：莫队算法

题目数据组数 $T$ 较大（可达 $2.5 \times 10^5$），且 $N+M$ 的总和也在 $2.5 \times 10^5$ 级别。
我们需要快速计算组合数前缀和 $S(n, k) = \sum_{i=0}^{k} C(n, i)$。

直接预处理所有前缀和不可行（空间和时间复杂度 $O(n^2)$）。这里采用莫队算法（Mo's Algorithm）的思想，通过离线排序询问，并利用递推关系动态维护当前的 $S(n, k)$ 值：

• $n$ 变化（轮数增减）：利用 $S(n, k)$ 与 $S(n \pm 1, k)$ 的递推公式进行转移。
• $k$ 变化（获胜上限增减）：直接加减对应的组合数值 $C(n, k)$。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7, MAXN = 250005;

ll fac[MAXN], ifac[MAXN];
int inv[MAXN];

// 快速幂：计算 (a^b) % MOD
ll power(ll a, ll b) {
    ll r = 1; 
    for (a %= MOD; b; b >>= 1, a = a * a % MOD) 
        if (b & 1) r = r * a % MOD;
    return r;
}

// 预处理阶乘、阶乘逆元、线性求逆元
void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; ++i) 
        fac[i] = fac[i-1] * i % MOD;
    
    ifac[MAXN-1] = power(fac[MAXN-1], MOD-2);
    for (int i = MAXN-2; i >= 0; --i) 
        ifac[i] = ifac[i+1] * (i+1) % MOD;
    
    inv[1] = 1;
    for (int i = 2; i < MAXN; ++i) 
        inv[i] = (MOD - MOD/i) * (ll)inv[MOD%i] % MOD;
}

// 组合数 C(n, k)
inline ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n-k] % MOD;
}

// 除以2的逆元，用于 n 减少时的逆运算
const ll INV2 = (MOD + 1) / 2;

struct Query {
    int n, K, id;
    bool is_m_le_n; // 标记属于哪种情况
    int orig_N, orig_M;
} q[MAXN];

ll ans[MAXN];
const int BLOCK = 500; // 分块大小，用于莫队排序

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    
    int T, P; 
    cin >> T >> P; // P' 表示概率 p，但本题解法中实际概率值不影响组合数计算（条件概率下所有合法序列等概率）
    
    // 读入询问并离线处理
    for (int i = 0; i < T; ++i) {
        int N, M; 
        cin >> N >> M;
        q[i].orig_N = N;
        q[i].orig_M = M;
        q[i].n = N + M; // 总轮数
        q[i].id = i;
        
        if (M <= N) {
            q[i].is_m_le_n = true;
            q[i].K = M - 1; // 计算 S(N+M-1, M-1)
        } else {
            q[i].is_m_le_n = false;
            q[i].K = N - 1; // 计算 S(N+M-1, N-1)
        }
    }
    
    // 莫队排序：按 n 分块，奇偶性优化
    sort(q, q + T, [](const Query& a, const Query& b) {
        int ba = a.n / BLOCK, bb = b.n / BLOCK;
        if (ba != bb) return ba < bb;
        return (ba & 1) ? a.K > b.K : a.K < b.K;
    });
    
    // 当前状态：cur_n 表示当前处理的总轮数-1，cur_K 表示当前的上限
    int cur_n = 0, cur_K = -1;
    ll cur_S = 0; // 当前维护的 S(cur_n, cur_K) 值
    
    // 莫队转移函数
    auto add_K = [&]() {
        // S(n, K) -> S(n, K+1): 加上 C(n, K+1)
        cur_K++;
        cur_S = (cur_S + C(cur_n, cur_K)) % MOD;
    };
    
    auto del_K = [&]() {
        // S(n, K) -> S(n, K-1): 减去 C(n, K)
        cur_S = (cur_S - C(cur_n, cur_K) + MOD) % MOD;
        cur_K--;
    };
    
    auto add_n = [&]() {
        // S(n, K) -> S(n+1, K): 递推公式 S(n+1,K) = 2*S(n,K) - C(n, K)
        cur_n++;
        cur_S = (2LL * cur_S - C(cur_n - 1, cur_K) + MOD) % MOD;
    };
    
    auto del_n = [&]() {
        // S(n, K) -> S(n-1, K): 逆推公式 S(n-1,K) = (S(n,K) + C(n-1, K)) / 2
        cur_S = (cur_S + C(cur_n - 1, cur_K)) % MOD * INV2 % MOD;
        cur_n--;
    };
    
    // 处理每个询问
    for (int i = 0; i < T; ++i) {
        int tn = q[i].n, tK = q[i].K;
        
        // 调整 K (获胜次数上限)
        while (cur_K < tK) add_K();
        while (cur_K > tK) del_K();
        
        // 调整 n (总轮数-1)
        while (cur_n < tn) add_n();
        while (cur_n > tn) del_n();
        
        ll S_val = (tK < 0) ? 0 : cur_S; // 处理边界情况
        
        int N = q[i].orig_N, M = q[i].orig_M;
        int n = N + M;
        ll den = C(n, N); // 分母：总方案数
        ll res;
        
        if (q[i].is_m_le_n) {
            // 情况1: M <= N
            // 结果 = (N-M) + S_val / den
            ll base = ((ll)(N - M) % MOD + MOD) % MOD;
            res = (base * den % MOD + S_val) % MOD;
            res = res * power(den, MOD-2) % MOD; // 乘以分母的逆元
        } else {
            // 情况2: M > N
            // 结果 = S_val / den
            res = S_val * power(den, MOD-2) % MOD;
        }
        ans[q[i].id] = res;
    }
    
    // 输出结果
    for (int i = 0; i < T; ++i) 
        cout << ans[i] << '\n';
    
    return 0;
}