自动搬运

查看原文

来自洛谷，原作者为

	_sry **

搬运于2025-08-24 21:58:17，当前版本为作者最后更新于2019-09-21 09:33:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意简述

小 $A$ 与小 $B$ 在玩游戏，已知小 $A$ 赢 $n$ 局，小 $B$ 赢 $m$ 局，没有平局情况，且赢加一分，输减一分，而若只有 $0$ 分仍输不扣分。

已知小 $A$ 每次赢得概率为 $p$ ，问小 $A$ 得分期望。 $T$ 组数据。

$T,n,m\leq 2.5\times 10^5$

$solution:$

因为赢场输场已经固定，所以 $p$ 其实是没有用，则现在考虑计算小 $A$ 得分总和。

将赢输场前缀和，记为 $\{s\}$，则得分为 $n-m-min\{s\}$ 。假设所有 $-1$ 均有意义，则分数为 $n-m$ 。

设 $min\{s\}=x$，则第一次出现 $-1,-2,…,x$ 均无意义因为当时得分前为 $0$ 而又被 $-1$，无意义，共出现 $|x|$ 次情况，即得分为 $n-m-min\{s\}$。

所以现在的问题转化为给定 $n$ 个 $1$ 与 $m$ 个 $-1$ ，问最小前缀和为 $w$ 的方案数。

基本操作，将问题转化为平面移动问题。

若要求最小前缀和为 $w$ 的方案数，可以表示为从 $(0,0)$ 走到 $(n,m)$ 的方案数，每次往上或左走一步求经过 $y=x+w$ 但不能经过 $y=x+w+1$ 直线的方案数。

考虑求从 $(1,1)$ 到 $(n,m)$ 经过 $y=x+w$ 的方案数，可以将第一次经过 $y=x+w$ 的交点之前部分对 $y=x+w$ 对称，则 $(0,0)$ 对称到 $(-w,w)$ ，可以发现每次从 $(-w,w)$ 到 $(n,m)$ 经交点对称后对应一条合法路径，则其方案数为 $\dbinom{n+m}{n+w}$ 。

通过简单容斥原理得到若最小前缀和为 $w$ 的方案数为 $\dbinom{n+m}{n+w}-\dbinom{n+m}{n+w+1}$ 。

考虑赢 $n$ 场输 $m$ 场的得分，得分区间为 $[max\{0,n-m\},n]$ 。

分类讨论 $n,m$ 大小。

若 $n\geq m$ ，则得分区间在 $[n-m,n]$ , $min\{s\}\in [-m,0]$。

$Ans=\sum_{i=0}^{m} (n-m+i) (\dbinom{n+m}{n+i}-\dbinom{n+m}{n+i+1})$

$$=(n-m) \sum_{i=0}^m(\dbinom{n+m}{n+i}-\dbinom{n+m}{n+i+1}) +\sum_{i=0}^m i\times (\dbinom{n+m}{m-i}-\dbinom{n+m}{m-i-1}) $$$$=(n-m)\dbinom{n+m}{n}+\sum_{i=0}^{m-1} \dbinom{n+m}{i} $$

若 $n<m$ ，则同理 $min\{s\}\in [{-m,n-m}]$

$$Ans=\sum_{i=m-n}^m (n-m+i)\times\dbinom{n+m}{m-i}-\dbinom{n+m}{m-i-1} $$$$=(n-m)\dbinom{n+m}{n}+\sum_{i=m-n}^m i\times \dbinom{n+m}{m-i}-\sum_{i=m-n}^{m-1} i\times \dbinom{n+m}{m-i-1} $$$$=(n-m)\dbinom{n+m}{n}+(m-n)\dbinom{n+m}{n}+\sum_{i=m-n+1}^m i\times \dbinom{n+m}{m-i}-\sum_{i=m-n}^{m-1} i\times \dbinom{n+m}{m-i-1} $$$$=\sum_{i=m-n+1}^{m-1} i\times\dbinom{n+m}{m-i}-\sum_{i=m-n+1}^{m} (i-1)\times \dbinom{n+m}{m-i+1} $$$$=\sum_{i=m-n+1}^{m} \dbinom{n+m}{m-i}$$ $$=\sum_{i=0}^{n-1}\dbinom{n+m}{i}$$

可以发现现在的问题为如何快速求 $F(n,k)=\sum_{i=0}^k \dbinom{n}{i}$

可以发现 $F(n,k)=\sum_{i=0}^k \dbinom{n-1}{i-1}+\dbinom{n-1}{i}=2\times F(n-1,k)-\dbinom{n-1}{k}$ 。即 $F(n,k)$ 与 $F(n-1,k)$ 和 $F(n,k-1)$ 都有递推关系。

直接将答案离线后莫队计算即可。

时间复杂度 $O((n+m)\sqrt{n+m})$ 。