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

· · 题解

题意简述

小 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}) 。