[2020 年百度之星·程式設計大賽 - 複賽] Battle for Wosneth

題解

Alice打一次加1,機率p%,Bod打一次加1機率q%

他們打一輪,期望得分p%-q%,有幾輪哪?

每輪Bod期望掉血p%,是以有m/(p%)輪,注意最後一輪Bod先挂了,沒法反擊

是以答案是(m/(p%) - 1) * (p%-q%) + 1 * p%

注意m/(p%)不一定是整數,變換一下

(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對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

你在打遊戲的時候碰到了如下問題：

​ 有兩個人記作Alice和Bob，Bob的生命值為mmm，Alice的生命值很高，是以可以認為是無限的。兩個人的攻擊命中率分别為p%,q%p%,q%p%,q%。兩個人輪流攻擊對方。從Alice開始攻擊，每次攻擊的時候，如果Alice命中，那麼能讓對方的生命值減低111，同時自己的生命值能恢複111，如果Bob命中，那麼能讓對方的生命值減低111，注意Bob不會自己回血。

直到Bob的血量變為000，遊戲結束。Alice想知道，遊戲結束的時候，自己期望生命值變化是多少，對998244353998244353998244353取模。

注意這裡的變化量不是絕對值，也就是如果50%50%50%的機率加一，50%50%50%的機率減一，那麼期望的變化量就是000。

對于一個分數a/ba/ba/b，其中gcd⁡(a,b)=1\gcd(a,b)=1gcd(a,b)=1，那麼我們認為這個分數對998244353998244353998244353取模的值為一個數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

第一行一個正整數T(1≤T≤104)T(1\leq T\leq 10^4)T(1≤T≤104)表示資料組數。

對于每組資料，第一行三個整數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

每組測試資料，輸出一個數，表示答案。

Sample Input

2
4 100 100
1 50 50
           

Sample Output

1
499122177

Hint
第一組資料中，每次都能命中，是以Alice能恢複 4 點生命值，減低 3 點生命值，變化量必定為 1。

第二組資料中，對應的分數為 1/2，在Alice命中Bob之前，Bob能期望命中Alice 1/2 次。