題解

Alice打一次加1,概率p%,Bod打一次加1概率q%
他們打一輪,期望得分p%-q%,有幾輪哪?
每輪Bod期望掉血p%,所以有m/(p%)輪,注意最后一輪Bod先掛了,沒法反擊

所以答案是(m/(p%) - 1) * (p%-q%) + 1 * p%
注意m/(p%)不一定是整數(shù),變換一下
(m-p * inv(100)) * (p-q) * inv ( p ) + p * inv(100)
其中inv(i)是mod998244353LL的乘法逆元

代碼

#include <iostream> #include <cstdio>using namespace std;typedef long long ll;void exgcd(ll a, ll b, ll &x, ll &y) //拓展歐幾里得算法 {if(!b)x = 1, y = 0;else{exgcd(b, a % b, y, x);y -= x * (a / b);} }ll Mod = 998244353LL;ll inv(ll a) //求a對(duì)b取模的逆元 {ll x, y;ll b = Mod;exgcd(a, b, x, y);return (x + b) % b; }int main() {int T;scanf("%d", &T);while (T--) {int m,p,q;scanf("%d%d%d",&m,&p,&q);ll tmp = (m-p*inv(100))%Mod*(p-q)%Mod*inv(p)%Mod;printf("%lld\n", ((tmp+p*inv(100))%Mod+Mod)%Mod);}return 0; }

Problem Description

你在打游戲的時(shí)候碰到了如下問題：

? 有兩個(gè)人記作Alice和Bob，Bob的生命值為mmm，Alice的生命值很高，所以可以認(rèn)為是無限的。兩個(gè)人的攻擊命中率分別為p%,q%p%,q%p%,q%。兩個(gè)人輪流攻擊對(duì)方。從Alice開始攻擊，每次攻擊的時(shí)候，如果Alice命中，那么能讓對(duì)方的生命值減低111，同時(shí)自己的生命值能恢復(fù)111，如果Bob命中，那么能讓對(duì)方的生命值減低111，注意Bob不會(huì)自己回血。

直到Bob的血量變?yōu)?00，游戲結(jié)束。Alice想知道，游戲結(jié)束的時(shí)候，自己期望生命值變化是多少，對(duì)998244353998244353998244353取模。

注意這里的變化量不是絕對(duì)值，也就是如果50%50%50%的概率加一，50%50%50%的概率減一，那么期望的變化量就是000。

對(duì)于一個(gè)分?jǐn)?shù)a/ba/ba/b，其中g(shù)cd?(a,b)=1\gcd(a,b)=1gcd(a,b)=1，那么我們認(rèn)為這個(gè)分?jǐn)?shù)對(duì)998244353998244353998244353取模的值為一個(gè)數(shù)c(0≤c<998244353)c(0\leq c < 998244353)c(0≤c<998244353)滿足bc≡a(mod998244353)bc\equiv a \pmod {998244353}bc≡a(mod998244353)。

Input

第一行一個(gè)正整數(shù)T(1≤T≤104)T(1\leq T\leq 10^4)T(1≤T≤104)表示數(shù)據(jù)組數(shù)。

對(duì)于每組數(shù)據(jù)，第一行三個(gè)整數(shù)m,p,q(1≤m≤109,1≤p,q≤100)m, p, q(1\leq m \leq 10^9, 1\leq p,q\leq 100)m,p,q(1≤m≤109,1≤p,q≤100)。

Output

每組測(cè)試數(shù)據(jù)，輸出一個(gè)數(shù)，表示答案。

Sample Input

2 4 100 100 1 50 50

Sample Output

1 499122177Hint 第一組數(shù)據(jù)中，每次都能命中，所以Alice能恢復(fù) 4 點(diǎn)生命值，減低 3 點(diǎn)生命值，變化量必定為 1。第二組數(shù)據(jù)中，對(duì)應(yīng)的分?jǐn)?shù)為 1/2，在Alice命中Bob之前，Bob能期望命中Alice 1/2 次。

總結(jié)

以上是生活随笔為你收集整理的[2020 年百度之星·程序设计大赛 - 复赛] Battle for Wosneth的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。