QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581958#9376. GamecbbdhzWA 85ms3576kbC++201.3kb2024-09-22 14:44:252024-09-22 14:44:26

Judging History

你现在查看的是最新测评结果

  • [2024-09-22 14:44:26]
  • 评测
  • 测评结果:WA
  • 用时:85ms
  • 内存:3576kb
  • [2024-09-22 14:44:25]
  • 提交

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'