问题分析

我们需要计算在已知 Alice 恰好赢了 $N$ 轮的条件下，她的最终得分的数学期望。这是一个条件期望问题。

算法思路

核心思想：组合数学 + 莫队算法

将问题转化为带边界的随机游走路径计数问题，使用莫队算法高效处理多组查询。

关键数学推导

设最终 Alice 的得分为 $k$，则：

• 如果 $N \geq M$，最小得分为 $N-M$（全胜）
• 如果 $N < M$，由于边界保护，最小得分为 $0$

期望值可以表示为：

$$E = \max(0, N-M) + \frac{\sum \text{路径权重}}{\text{总路径数}} $$

其中路径计数与卡特兰数相关。

代码详解

1. 预处理组合数

const int N = 500010, mod = 1e9 + 7;
int fac[N], inv[N];

// 快速幂
int qmi(int a, int b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod, b /= 2;
    }
    return ret;
}

// 组合数计算
int C(int n, int m) {
    if (n < m || n < 0) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

2. 莫队算法框架

将查询按块排序，利用相邻查询间的相关性减少计算量：

struct node {
    int n, m;    // n = N+M, m = min(N,M)-1
    int id, lst; // id: 查询编号, lst: C(N+M, N)
} q[N];

bool cmp(node a, node b) {
    int id1 = (a.n - 1) / len + 1, id2 = (b.n - 1) / len + 1;
    if (id1 != id2) return id1 < id2;
    return (id1 & 1) ? a.m < b.m : a.m > b.m;
}

3. 状态转移操作

维护当前状态 $(n, m)$ 和对应的组合数值 $nw$：

// 增加 n（总轮数+1）
void addn() {
    nw = (nw * 2 - C(n, m) + mod) % mod, n++;
}

// 增加 m（min(N,M)-1 增加）
void addm() {
    nw = (nw + C(n, m + 1)) % mod, m++;
}

// 减少 n
void deln() {
    nw = (nw + C(n - 1, m)) % mod * (mod + 1) / 2 % mod, n--;
}

// 减少 m  
void delm() {
    nw = (nw - C(n, m) + mod) % mod, m--;
}

4. 主算法流程

// 初始化基本答案
for (int i = 1; i <= t; i++) {
    int x, y;
    cin >> x >> y;
    q[i] = {x + y, min(x, y) - 1, i, C(x + y, y)};
    ans[i] = max(0ll, x - y);  // 基础得分
}

// 莫队处理
len = 600, n = 1, nw = 1;
sort(q + 1, q + t + 1, cmp);

for (int i = 1; i <= t; i++) {
    // 调整到目标状态
    while (n < q[i].n) addn();
    while (n > q[i].n) deln();
    while (m < q[i].m) addm();
    while (m > q[i].m) delm();
    
    // 计算最终答案
    (ans[q[i].id] += nw * qmi(q[i].lst, mod - 2) % mod) %= mod;
}

算法原理

组合意义

$nw$ 维护的是某种路径计数的和，具体来说：

• $n = N + M$（总轮数）
• $m = \min(N, M) - 1$
• $nw$ 与"不超过边界"的路径数相关

状态转移的数学基础

转移公式基于组合恒等式：

• addn: $f(n,m) = 2f(n-1,m) - C(n-1,m)$
• addm: $f(n,m) = f(n,m-1) + C(n,m)$
• deln: $f(n-1,m) = \frac{f(n,m) + C(n-1,m)}{2}$
• delm: $f(n,m-1) = f(n,m) - C(n,m)$

最终答案计算

期望值 = 基础得分 + 调整项：

$$\text{答案} = \max(0, N-M) + \frac{nw}{C(N+M, N)} \mod (10^9+7) $$

复杂度分析

预处理

• 阶乘和逆元：$O(N)$，$N = 5\times 10^5$
• 单次组合数查询：$O(1)$

莫队算法

• 排序：$O(T \log T)$
• 总状态转移：$O(T \sqrt{T})$，其中 $\sqrt{T} \approx 500$
• 单次查询：平均 $O(\sqrt{T})$

总复杂度

$O(N + T \sqrt{T})$，适合 $T \leq 2.5\times 10^5$ 的数据规模。

正确性保证

1. 数学推导严谨：基于组合恒等式和反射原理
2. 边界处理正确：考虑到了得分为负时的特殊规则
3. 模运算安全：使用模逆元处理除法，避免精度问题
4. 算法完备性：莫队算法确保所有查询被正确处理

算法优势

1. 高效性：利用查询间的相关性大幅减少计算量
2. 通用性：适用于大范围的 $N, M$ 取值
3. 精确性：基于组合数学的精确计算，无精度误差
4. 可扩展性：框架易于理解和修改

总结

本题通过巧妙的组合数学推导和莫队算法应用，高效解决了条件概率下的期望计算问题。核心创新在于：

• 将概率问题转化为路径计数问题
• 利用组合恒等式实现高效状态转移
• 使用莫队算法处理大规模查询

该解法在数学严谨性和算法效率之间取得了良好平衡，体现了组合数学与算法设计的完美结合。