2020 年百度之星·程序设计大赛 - 复赛 1001Battle for Wosneth

problem

Battle for Wosneth Accepts: 1174 Submissions: 5432
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
你在打游戏的时候碰到了如下问题：

​ 有两个人记作Alice和Bob，Bob的生命值为mm，Alice的生命值很高，所以可以认为是无限的。两个人的攻击命中率分别为p%,q%p%,q%。两个人轮流攻击对方。从Alice开始攻击，每次攻击的时候，如果Alice命中，那么能让对方的生命值减低11，同时自己的生命值能恢复11，如果Bob命中，那么能让对方的生命值减低11，注意Bob不会自己回血。

直到Bob的血量变为00，游戏结束。Alice想知道，游戏结束的时候，自己期望生命值变化是多少，对998244353998244353取模。

注意这里的变化量不是绝对值，也就是如果50%50%的概率加一，50%50%的概率减一，那么期望的变化量就是00。

对于一个分数a/ba/b，其中\gcd(a,b)=1gcd(a,b)=1，那么我们认为这个分数对998244353998244353取模的值为一个数c(0\leq c < 998244353)c(0≤c<998244353)满足bc\equiv a \pmod {998244353}bc≡a(mod998244353)。

Input
第一行一个正整数T(1\leq T\leq 10^4)T(1≤T≤10
4
)表示数据组数。

对于每组数据，第一行三个整数m, p, q(1\leq m \leq 10^9, 1\leq p,q\leq 100)m,p,q(1≤m≤10
9
,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 次。

solution

#include<iostream>
using namespace std;

typedef long long LL;
#define mod 998244353
#define maxn 200010

LL power(LL a, LL b){
	LL ret = 1;
	for(; b; b>>=1,a=a*a%mod)
		if(b&1)ret=ret*a%mod;
	return ret;
}

int main(){
	int T; cin>>T;
	int inv = power(100,mod-2);
	while(T--){
		int m,p,q; cin>>m>>p>>q;
		p = (LL)p*inv%mod;
		q = (LL)q*inv%mod;
		int ans = m-q*(m*power(p,mod-2)%mod+mod-1)%mod;
		cout<<((ans%mod+mod)%mod)<<"\n";
	}
	return 0;
}

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/107901666