QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581315#9376. GamecbbdhzTL 0ms3540kbC++202.5kb2024-09-22 11:49:252024-09-22 11:49:26

Judging History

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

  • [2024-09-22 11:49:26]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3540kb
  • [2024-09-22 11:49:25]
  • 提交

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;
}
int dfs_iterative(int chou1, int chou2, int p1, int p2) {
    stack<tuple<int, int>> st;
    map<pair<int, int>, int> dp; // 用来存储状态的结果

    st.push({ chou1, chou2 });
    dp[{chou1, chou2}] = -1; // -1 表示该状态尚未处理

    while (!st.empty()) {
        auto [chou1, chou2] = st.top();

        // 如果已经计算过了,直接跳过
        if (dp[{chou1, chou2}] != -1) {
            st.pop();
            continue;
        }

        // 终止条件
        if (chou1 <= 0) {
            dp[{chou1, chou2}] = 0;
            st.pop();
            continue;
        }
        if (chou2 <= 0) {
            dp[{chou1, chou2}] = 1;
            st.pop();
            continue;
        }

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

        // 子状态
        int nm1 = gcd(chou1, chou2 - chou1);
        int nm2 = gcd(chou1 - chou2, chou2);

        // 如果子状态还没计算过,先压入栈中
        if (dp.find({ chou1 / nm1, (chou2 - chou1) / nm1 }) == dp.end()) {
            st.push({ chou1 / nm1, (chou2 - chou1) / nm1 });
            dp[{chou1 / nm1, (chou2 - chou1) / nm1}] = -1;
        }
        if (dp.find({ (chou1 - chou2) / nm2, chou2 / nm2 }) == dp.end()) {
            st.push({ (chou1 - chou2) / nm2, chou2 / nm2 });
            dp[{(chou1 - chou2) / nm2, chou2 / nm2}] = -1;
        }

        // 如果所有子状态都处理完毕,处理当前状态
        if (dp[{chou1 / nm1, (chou2 - chou1) / nm1}] != -1 &&
            dp[{(chou1 - chou2) / nm2, chou2 / nm2}] != -1) {
            dp[{chou1, chou2}] = ((ll)pa * dp[{chou1 / nm1, (chou2 - chou1) / nm1}] % mod +
                (ll)pb * dp[{(chou1 - chou2) / nm2, chou2 / nm2}] % mod) % mod;
            st.pop();
        }
    }

    return dp[{chou1, chou2}];
}

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_iterative(a, b, x, y) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time 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: