题解：[CODEPLUS 2018 3 月赛] 博弈论与概率统计
题目难度：NOI/NOI+/CTSC
时间限制：1.00s
内存限制：512MB
题目大意
Alice 和 Bob 进行 N+MN+MN+M 轮游戏。已知 Alice 恰好赢了 NNN 轮，输了 MMM 轮。初始分数为 0，赢一轮加 1 分，输一轮扣 1 分。但如果分数为 0 时输掉比赛，则分数不变（对方照常加分）。
求游戏结束时 Alice 得分的数学期望，结果对 109+710^9+7109+7 取模。
解题思路
1. 问题转化
如果没有“0 分不扣分”的规则，Alice 的最终得分就是 N−MN - MN−M。
由于有了“0 分不扣分”的限制，每当 Alice 在 0 分时输掉比赛，她的实际得分会比理论得分 N−MN-MN−M 多 1（因为本该扣分但没扣）。
因此，最终得分 = N−M+N - M +N−M+（在 0 分时输掉的局数）。
我们需要计算在所有 CN+MNC_{N+M}^NCN+MN 种胜负序列中，Alice 在 0 分状态输掉比赛的期望次数。
2. 组合计数与分类讨论
设 S(n,k)S(n, k)S(n,k) 表示在 nnn 轮游戏中，Alice 获胜次数不超过 kkk 的方案数（即前缀和）。
根据 NNN 和 MMM 的大小关系，分两种情况讨论：
* 情况一：M≤NM \le NM≤N (输的局数少于赢的局数)
* 此时 N−M≥0N-M \ge 0N−M≥0，Alice 的分数很难长时间维持在 0。
* 期望得分公式推导为：E=(N−M)+S(N+M−1,M−1)CN+MNE = (N-M) + \frac{S(N+M-1, M-1)}{C_{N+M}^N}E=(N−M)+CN+MN S(N+M−1,M−1) 。
* 情况二：M>NM > NM>N (输的局数多于赢的局数)
* 此时 Alice 必定会多次回到 0 分并面临扣分。
* 期望得分公式推导为：E=S(N+M−1,N−1)CN+MNE = \frac{S(N+M-1, N-1)}{C_{N+M}^N}E=CN+MN S(N+M−1,N−1) 。
3. 算法优化：莫队算法
题目数据组数 TTT 较大（可达 2.5×1052.5 \times 10^52.5×105），且 N+MN+MN+M 的总和也在 2.5×1052.5 \times 10^52.5×105 级别。
我们需要快速计算组合数前缀和 S(n,k)=∑i=0kC(n,i)S(n, k) = \sum_{i=0}^{k} C(n, i)S(n,k)=∑i=0k C(n,i)。
直接预处理所有前缀和不可行（空间和时间复杂度 O(n2)O(n^2)O(n2)）。这里采用莫队算法（Mo's Algorithm）的思想，通过离线排序询问，并利用递推关系动态维护当前的 S(n,k)S(n, k)S(n,k) 值：
* nnn 变化（轮数增减）：利用 S(n,k)S(n, k)S(n,k) 与 S(n±1,k)S(n \pm 1, k)S(n±1,k) 的递推公式进行转移。
* kkk 变化（获胜上限增减）：直接加减对应的组合数值 C(n,k)C(n, k)C(n,k)。
代码实现
