OI - Best-of-(2n-1) (AtCoder)

随便刷了一点题,然后点开这场 M-Solution,在 C 题就被卡住了,看来数学仍然是一个弱点。


Part1. 题面

A 和 B 玩游戏,已知在这个游戏中,A 获胜的概率为 $a\%$,B 获胜的概率为 $b\%$,平局(没有人获胜)的概率是 $c\%$。

当某一个人获胜恰好 n 场后,游戏结束。求在游戏结束前,进行的游戏场数的期望。

数据规模:$1\le n\le10^5,a+b+c=100$。


Part2. 解析

下面的小写字母 $a,b,c$ 分别代替题面中的 $a\%,b\%,c\%$

显然是一道数学题……不妨把 A,B 分别获胜的场数表示成二元组 $(p,q)$,即 A 获胜 p 场,B 获胜 q 场。

但是我们发现平局非常麻烦……但是可以发现,如果 已知非平局的场数(且最后一次游戏是非平局的),求在这种情况下,进行的游戏场数的期望。定义函数 $h(i)$ 表示 恰好 进行了 i 场非平局的游戏时,进行的游戏场数的期望。

可以得到一个比较简单的式子:

然后移一下项:

因为游戏开局时,就已经是“恰好进行了0局非平局游戏”的局面,所以 $h(0)=0$,然后可以得到 $h(i)=\frac i{1-c}$。

然后发现答案还剩了一部分:游戏结束时恰好进行了 i 场非平局游戏的概率,定义这个概率为 $P(i)$。那么最后答案就是:

(上面这个式子中 i 的实际意义是游戏结束时,失败的那一个玩家的获胜场数)

那么如何求 $P(i+n)$?不妨设游戏结束时 A 获胜(B 获胜就反过来)。因为 只考虑分出胜负的局面,所以定义新的概率为 $a’=\frac a{a+b}$,$b’=\frac b{a+b}$,分别表示 A,B 在没有平局的情况下获胜的概率。

然后 $P(i+n)$ 中,A 获胜了 n 次,B 获胜了 i 次,这是对于一个游戏过程的概率。还要考虑有多少个游戏过程的结果是 $i+n$ —— 因为 最后一次一定是 A 获胜,所以在前 n+i-1 场游戏中,A 获胜了 n-1 次,B 获胜了 i 次,所以有 $C_{n+i-1}^i$ 个游戏过程对应了 $P(i+n)$ 这一个游戏结果。

再计算 B 获胜的概率,就是反过来,也就是说 $P(i+n)=\left[(a’)^n(b’)^i+(a’)^i(b’)^n\right]C_{n+i-1}^i$。

最后的答案就是:

注意里面是 $a’,b’$ 不是 $a,b$!


Part3. 源代码

这种题的码量都很小嘛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5,MOD=1e9+7;
typedef long long ll;
#define fix(cur) (int((cur%MOD+MOD)%MOD))

struct MODNUM{
int num;
MODNUM(){}
MODNUM(int _num):num(_num){}
MODNUM operator *(const MODNUM cur)const{return fix(1ll*num*cur.num);}
MODNUM operator +(const MODNUM cur)const{return fix(1ll*num+cur.num);}
MODNUM operator -(const MODNUM cur)const{return fix(1ll*num-cur.num);}
MODNUM operator *=(const MODNUM cur){return *this=(*this)*cur;}
MODNUM operator +=(const MODNUM cur){return *this=(*this)+cur;}
MODNUM operator -=(const MODNUM cur){return *this=(*this)-cur;}
}Cfac[2*N+3],Cinv[2*N+3],Cone(1);
MODNUM QPow(MODNUM und,int cur){
MODNUM resu(1);
while(cur){
if(cur&1) resu*=und;
und*=und;
cur>>=1;
}
return resu;
}
MODNUM fC(int cura,int curb){return Cfac[curb]*Cinv[cura]*Cinv[curb-cura];}

int n,Ia,Ib,Ic;

void Init(){
Cfac[0]=1;for(int i=1;i<=2*N;i++) Cfac[i]=Cfac[i-1]*i;
Cinv[2*N]=QPow(Cfac[2*N],MOD-2);for(int i=2*N-1;i>=0;i--) Cinv[i]=Cinv[i+1]*(i+1);
}
int main(){
Init();
scanf("%d%d%d%d",&n,&Ia,&Ib,&Ic);
MODNUM Phaf=QPow(Ia+Ib,MOD-2)*Ia,ans=0,Pc=QPow(100,MOD-2)*Ic;
for(int i=0;i<n;i++)
ans+=fC(i,n-1+i)*(QPow(Phaf,n)*QPow(Cone-Phaf,i)+QPow(Phaf,i)*QPow(Cone-Phaf,n))*(i+n)*QPow(Cone-Pc,MOD-2);
printf("%d\n",ans);
return 0;
}

The End

Thanks for reading!

开始频更博客 :)

0%