题解：P4260 [Code+#3] 博弈论与概率统计

· · 题解

观察到 p 是无效的，因此期望值为总得分除以总方案数。总方案数显然是 n+m \choose n，接下来考虑总得分的计算。

我们发现这个得分非负的限制很特殊，考虑从这个地方入手。不妨设得分小于 0 的次数为 i，那么显然这一局的得分就是 n-m+i，我们现在要算出这个东西的方案数。

如果对这类计数问题足够敏感，容易发现这个问题可以放在平面直角坐标系内进行刻画。考虑赢一场等价于横坐标 +1，输一场等价于纵坐标 +1。由于 n-m+i \ge 0 \Rightarrow m \le n+i \Rightarrow y \le x+i，则问题转化为从 (0,0) 走到 (n,m)，且不越过 y=x+i 的方案数。

套路的，我们将不越过 y=x+i 转化为不与 y=x+i+1 相交，把 (n,m) 对称过来得到 (m-i-1,n+i+1)，则方案数即为 {n+m \choose m} - {n+m \choose m-i-1}。

这个是至多 i 次的方案，我们需要得到恰好 i 次的（因为是加权求和），所以方案数应为 {n+m \choose m-i} - {n+m \choose m-i-1}

然后我们就可以计算总得分了。其实到这里我们已经拥有了一个 O(T(n+m)) 的做法，但是无法接受。考虑从数学上优化之。

由于 n,m 的大小关系未知，所以得分的上下界会有所改变，考虑分类讨论和推式子：

\sum_{i=0}^m (n-m+i) \times \left( {n+m \choose m-i} - {n+m \choose m-i-1} \right) \\ = \sum_{i=0}^m (n-m+i) \times {n+m \choose m-i} - \sum_{i=0}^m (n-m+i) \times {n+m \choose m-i-1}

换元，令 k=m-i，得：

\sum_{k=0}^m (n-k) \times {n+m \choose k} - \sum_{k=0}^m (n-k) \times {n+m \choose k-1}

再次换元，令 j=k-1，当 k=0 时 j=-1，这一项为 0 可以忽略，同时把第一个 \sum 的变量换成 j，于是得到：

\sum_{j=0}^m (n-j) \times {n+m \choose j} - \sum_{j=0}^{m-1} (n-j-1) \times {n+m \choose j} \\ = \sum_{j=0}^m (n-j) \times {n+m \choose j} - \sum_{j=0}^{m-1} (n-j-1) \times {n+m \choose j}

拆开第一项来得到前缀和形式：

= (n-m) \times {n+m \choose n} + \sum_{j=0}^{m-1} (n-j) \times {n+m \choose j} - \sum_{j=0}^{m-1} (n-j-1) \times {n+m \choose j} \\ = (n-m) \times {n+m \choose n} + \sum_{i=0}^{m-1} {n+m \choose i} \sum_{i=m-n}^m (n-m+i) \times \left( {n+m \choose m-i} - {n+m \choose m-i-1} \right) \\ = \sum_{i=m-n}^m (n-m+i) \times {n+m \choose m-i} - \sum_{i=m-n}^m (n-m+i) \times {n+m \choose m-i-1} \\

依旧换元令 k=m-i，j=k-1：

\sum_{k=0}^n (n-k) \times {n+m \choose k} - \sum_{k=0}^n (n-k) \times {n+m \choose k-1} \\ = \sum_{j=0}^n (n-j) \times {n+m \choose j} - \sum_{j=0}^{n-1} (n-j-1) \times {n+m \choose j}

拆开第一项得（j=n 时第一项为 0，省略）：

= \sum_{j=0}^{n-1} (n-j) \times {n+m \choose j} - \sum_{j=0}^{n-1} (n-j-1) \times {n+m \choose j} \\ = \sum_{j=0}^{n-1} {n+m \choose j}

现在我们成功的将两者化为了组合数的前缀和形式，接下来是一步神奇的优化：考虑莫队维护这个前缀和，将每个测试用例看作一个询问去解决。

具体而言，我们维护左端点 l 表示 n+m，右端点 r 表示 \sum 的上标。其中右端点的移动是简单的，直接加上或减去相应的组合数即可。

而左端点的移动有一点实现细节。它需要加上 {l+1 \choose j}，这个可以根据组合数递推公式拆成 {l \choose j} + {l \choose j-1}。我们现在知道 now = \sum_{i=0}^{r} {l \choose i}，显然将其拆开就能得到 now - {l \choose r} = \sum_{i=0}^{r-1} {l \choose i} = \sum_{i=0}^{r} {l \choose i-1}，所以更新后的答案就是 2 \times now - {l \choose r}。

至此我们做完了此题，时间复杂度 O((n+m)\sqrt{T})。代码实现并不复杂。

最后，总结一下我们在这个题目中学到了什么：