QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#581958 | #9376. Game | cbbdhz | WA | 85ms | 3576kb | C++20 | 1.3kb | 2024-09-22 14:44:25 | 2024-09-22 14:44:26 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
// 快速幂计算 a^b % mod
int qp(int a, int b, int mod) {
int ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return ans;
}
// 递归计算 Alice 获胜概率
int dfs(int x, int y, int p1, int p2, int temp) {
if (y == 0) {
return 1;
}
else if (x == y) {
return p1 * temp % mod;
}
else if (x > y) {
int t = x / y;
if (x % y == 0) {
t--;
}
return (1 - qp(p2 * temp, t, mod) * (1 - dfs(x - t * y, y, p1, p2, temp)) % mod + mod) % mod;
}
else { // x < y
int t = y / x;
if (y % x == 0) {
t--;
}
return qp(p1 * temp % mod, t, mod) * dfs(x, y - t * x, p1, p2, temp) % mod;
}
}
// 处理每个测试用例
void solve() {
int x, y;
cin >> x >> y;
int a, b, c;
cin >> a >> b >> c;
// 计算 p0 和 p1 的系数
int temp = qp(a + b, mod - 2, mod);
cout << dfs(x, y, a, b, temp) << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
3 1 1 2 2 6 1 3 2 3 6 3 4 7 3 15
output:
499122177 910398850 220911476
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 85ms
memory: 3572kb
input:
100000 1 1000000000 12980050 128257807 266126484 1 1000000000 400255084 123438563 768881284 1000000000 1000000000 24563487 72082135 450057094 1 1000000000 56952077 40876000 193815114 1000000000 1000000000 82048274 239365585 326520865 1000000000 1 309821265 346013425 963168258 1 1 104158269 199365020...
output:
947058399 376449942 612621163 138416357 592200562 60437625 870227707 169499045 443740538 415694940 793062945 951368934 426243016 864656779 750317399 710811499 486881524 824329239 198191519 189360084 966510181 512645443 695650039 43612881 550002158 408876471 246877045 39876086 667870434 405196653 593...
result:
wrong answer 6th lines differ - expected: '45779380', found: '60437625'