QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581301#9376. GamecbbdhzML 0ms3480kbC++201.7kb2024-09-22 11:43:562024-09-22 11:43:57

Judging History

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

  • [2024-09-22 11:43:57]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3480kb
  • [2024-09-22 11:43:56]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;

int qp(int a, int b, int mod) {
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans = (ll)ans * a % mod;
        }
        b >>= 1;
        a = (ll)a * a % mod;
    }
    return ans;
}

// 记忆化存储已经计算过的状态
unordered_map<ll, int> memo;

// 用于合并 chou1 和 chou2 为一个唯一的键
ll combine(int chou1, int chou2) {
    return (ll)chou1 * 1000000000LL + chou2;
}

int dfs(int chou1, int chou2, int p1, int p2) {
    if (chou1 <= 0) {
        return 0;
    }
    if (chou2 <= 0) {
        return 1;
    }

    ll key = combine(chou1, chou2);
    if (memo.count(key)) {
        return memo[key];
    }

    int temp = qp(p1 + p2, mod - 2, mod); // 计算 (p1 + p2) 的逆元
    int pa = (ll)p1 * temp % mod; // Alice 赢的概率
    int pb = (ll)p2 * temp % mod; // Bob 赢的概率

    int nm1 = gcd(chou1, chou2 - chou1);
    int nm2 = gcd(chou1 - chou2, chou2);

    // 递归调用,注意对结果取模
    memo[key] = ((ll)pa * dfs(chou1 / nm1, (chou2 - chou1) / nm1, p1, p2) % mod +
                 (ll)pb * dfs((chou1 - chou2) / nm2, chou2 / nm2, p1, p2) % mod) % mod;

    return memo[key];
}

void solve() {
    int a, b;
    cin >> a >> b;
    int temp = gcd(a, b);
    a /= temp;
    b /= temp;
    int x, y, z;
    cin >> x >> y >> z;
    cout << dfs(a, b, x, y) << endl;
}

signed main() {
    ios::sync_with_stdio(false); 
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        memo.clear();  // 每个测试用例清空记忆化数组
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3480kb

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
Memory Limit Exceeded

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:


result: