随便刷了一点题，然后点开这场 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
|
#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!
开始频更博客 :)