6838. BattleForWosneth

HDOJ 6838. BattleForWosneth

2020 年百度之星·程序设计大赛 - 复赛

• 6838. BattleForWosneth

题目：6838. BattleForWosneth

问题描述：

你在打游戏的时候碰到了如下问题：

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

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

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

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

输入：

第一行一个正整数T(1≤T≤104)表示数据组数。
对于每组数据，第一行三个整数m,p,q(1≤m≤109,1≤p,q≤100)。

输出：

每组测试数据，输出一个数，表示答案。

样本输入：

2
4 100 100
1 50 50

样本输出：

1
499122177

样本输入：

• 第一组数据中，每次都能命中，所以Alice能恢复 4 点生命值，减低 3 点生命值，变化量必定为 1。
• 第二组数据中，对应的分数为 1/2，在Alice命中Bob之前，Bob能期望命中Alice 1/2 次。

方法：扩展欧几里得

思路：把 p 和 q 当作攻击力，那么 Alice需要攻击 m / p 个回合才能结束，由于最后一个回合，Alice攻击完就结束了，所以Bob只攻击了 m / p - 1 个回合，所以前 m / p - 1个回合Alice的生命值变化为 (m / p - 1) * (p - q)，最后一个回合Alice的生命值变化为 p ，因此Alice的生命值的总变化为 (m / p - 1) * (p - q) + p，由于p和q原来均表示概率需要除以100，为了避免计算过程中出现小数和丢失精度的情况，可采用逆元将原本的除装换成乘，根据题目要求取余并将公式简化得到最终计算公式(m - p * inv(100)) % MOD * (p - q) % MOD * inv(p) % MOD + p * inv(100)，本题使用扩展欧几里得求逆元。

运行数据：执行用时：2823MS，内存消耗：13820K

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

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		long MOD= 998244353;
		
		while (T-- > 0) {
			int m = sc.nextInt();
			long p = sc.nextLong();
			long q = sc.nextLong();
			
			long result = (m - p * inv(100)) % MOD * (p - q) % MOD * inv(p) % MOD + p * inv(100);
			System.out.println((result + MOD) % MOD);
		}
	}
	
	private static long x,y;
	
	// 拓展欧几里得算法
	private static void exgcd(long a,long b){
		if(b == 0){
			x = 1;
			y = 0;
			return;
		}
		exgcd(b,a % b);
		long k = x;
		x = y;
		y = k - a / b* y;
	}
	
	// 求逆元
	private static long inv(long a) {
	    long b = 998244353;
	    exgcd(a, b);
	    return (x + b) % b;
	}
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！