description
\(T\) 次询问，每次给定 \(n,m,p\)，总共 \(n+m\) 局游戏，每局 A 有 \(p\) 的概率获胜。一局游戏获胜 A 的得分加 1，否则减 1，但是如果 A 在得分为 0 的情况下输了一局，得分不变。求 A 赢 \(n\) 局，输 \(m\) 局后游戏结束时 A 的得分的数学期望。
- \(n,m,T\leq 2.5\times 10^5\)
solution
首先发现 \(p\) 是诈骗的，由于 \(n,m\) 是已知的，一个的游戏方案的概率就是 \(\dfrac{n!m!}{(n+m)!}\)，只需要算出所有游戏方案的最终得分和即可。
根据游戏规则，如果 A 在得分为 0 的情况下输，得分不变，我们称一局这样的情况为免疫。
如果整场游戏中 A 免疫了 \(k\) 次（显然 \(k\leq m\)），那么 A 的最终得分就是 \(n-m+k\)。于是我们可以对于每种免疫次数计算方案数。
先来考虑免疫 0 次的方案数计算。
把游戏过程当做 01 序列，0 表示 A 获胜，1 表示 A 输。则要求任意前缀中 1 的个数要小于等于 0 的个数。
先来算不合法的方案，构造双射：设序列前 \(i\) 个数中 0 的数量为 \(f_i\)，1 的数量为 \(g_i\)，找到第一个 \(f_i<g_i\) 的位置，则一定有 \(f_i=g_i-1\)，再将该位置（不包含）后面的所有 01 取反，得到一个含 \(m-1\) 个 0，\(n+1\) 个 1 的序列；反过来，任意一个含 \(m-1\) 个 0，\(n+1\) 个 1 的序列也对应一个不合法的序列。所以不合法的序列的方案数就是 \(\dbinom{n+m}{n+1}\)。合法的序列方案数就是 \(\dbinom{n+m}{n}-\dbinom{n+m}{n+1}\)。
同理，考虑免疫 \(k\) 次的方案数。依然是用 01 序列考虑，那么方案数是否就是任意前缀中 1 的个数都要小于等于 \(k\) 加 0 的个数的方案数呢？需要注意，我们应该求恰好免疫 \(k\) 次的方案数，而这样算出的是至多免疫 \(k\) 次的方案数，还要减去至多免疫 \(k-1\) 次的方案数，为 \(\dbinom{n+m}{n+k}-\dbinom{n+m}{n+k+1}\)。
需要注意 \(n+k<m\) 时方案数是 0，按照上面的方式构造是有问题的，所以 \(k\) 至少为 \(\max(0,m-n)\)。
综上，得分和就是 \(\sum\limits_{k=\max(0,m-n)}^m (n-m+k)\times(\dbinom{n+m}{n+k}-\dbinom{n+m}{n+k+1})\)。
开始推式子。
前面的系数里的 \(n-m\) 是常数，提出来。
变成计算 \(\sum\limits_{k=\max(0,m-n)}^m\dbinom{n+m}{n+k}-\dbinom{n+m}{n+k+1}\) 和 \(\sum\limits_{k=\max(0,m-n)}^m k\times(\dbinom{n+m}{n+k}-\dbinom{n+m}{n+k+1})\)。前者就等于 \(\dbinom{n+m}{n+\max(0,m-n)}\)，可直接计算；后者等于 \(\max(0,m-n)\times \dbinom{n+m}{n+\max(0,m-n)}+\sum\limits_{k=n+\max(0,m-n)+1}^{n+m}\dbinom{n+m}{k}\)。右边这个就是 \(2^{n+m}-\sum\limits_{k=0}^{n+\max(0,m-n)}\dbinom{n+m}{k}\)。
问题转化成了多次询问，求组合数前缀和。考虑莫队。
设 \(S_{l,r}=\sum\limits_{i=0}^l \dbinom{r}{i}\)。
有转移：
-
\(S_{l+1,r}=S_{l,r}+\dbinom{r}{l+1}\)
-
\(S_{l,r+1}=2S_{l,r}-\dbinom{r}{l}\)
第一个转移显然，第二个转移可以根据组合恒等式 \(\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}\) 得出。
时间复杂度线性乘根号。