2024icpc(Ⅱ)网络赛补题 G

2024icpc(Ⅱ)网络赛补题 G

题目链接：The 2024 ICPC Asia EC Regionals Online Contest (II)

G、Game

题意：

给定Alice和Bob的每一轮的概率$p_0,p_1$

给定Alice和Bob的初始数字$x,y$。

对于每一轮：

• 如果Alice获胜，则bob的数字$y$需要减去$x$。（如果$y\le 0$，Alice获胜）
• 如果Bob获胜，则Alice的数字$x$需要减去$y$。（如果$x\le 0$，Bob获胜）

重复上述游戏，直到出现胜利者。

问，Alice最终能赢得游戏的概率有多大。

思路：

可以直接用减法模拟，用除法加速，类似辗转相除法

当$x>y$时，$x$可以输$x/y$场，转移到$(x\%y,y)$的状态，其他状态A必胜

当$x\ge y$时，$x$必须赢$y/x$场，转移到$(x,x\%y)$的状态，然后在考虑A必胜的情况

代码：

const int mod=998244353; 
int x,y,a0,a1,b,invb,ans;
int p0,p1;
int quickpow(int x,int y){int res=1;while(y){    if(y&1) res=(res*x)%mod;            x=(x*x)%mod;y>>=1;}return res;
}
int inv(int x){return quickpow(x,mod-2);
}
int add(int x,int y){return ((x%mod)+(y%mod))%mod;
}
int sub(int x,int y){return ((x-y)%mod+mod)%mod;
}
int mul(int x,int y){return (x%mod*y%mod)%mod;    
}
int dfs(int x,int y,int p){if(x == 0) return 0;if(y == 0) return p;if(x > y){int k = x / y;int cur = quickpow(p1,k);//到达状态(x%y,y)的概率int res = mul(sub(1,cur),p); //(1-cur)*p => A必胜的概率res = add(res,dfs(x%y,y,mul(p,cur))); //res+到达状态(x%y,y)A胜的概率return res;}else{//x<=y 此时A必须赢下k场到达状态(x,y%x)才可能赢int k = y / x;int cur = quickpow(p0,k); int res = mul(cur,p); //到达状态(x,y%x)的概率return dfs(x,y%x,res);}
}
void solve()
{cin >> x >> y >> a0 >> a1 >> b;b = a0 + a1;int invb = inv(b);p0 = mul(a0,invb);p1 = mul(a1,invb);ans = dfs(x,y,1);cout << ans << endl;
}