QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591658#9376. GamelamkappaTL 0ms3564kbC++201.2kb2024-09-26 17:06:122024-09-26 17:06:12

Judging History

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

  • [2024-09-26 17:06:12]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3564kb
  • [2024-09-26 17:06:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr i64 M = 998244353;

i64 qpow(i64 x, i64 y=M-2){
    i64 res = 1;
    while(y){
        if(y & 1) res = res*x%M;
        x = x*x%M;
        y >>= 1;
    }
    return res;
}

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

    int T = 1;
    cin >> T;
    while(T--){
        i64 x, y; cin >> x >> y;
        i64 a0, a1, b; cin >> a0 >> a1 >> b;
        i64 p0 = a0 * qpow(a0+a1) % M;
        i64 p1 = a1 * qpow(a0+a1) % M;

        auto T = make_pair(x, y);
        i64 px = 0, py = 0, pl = 1;
        do{
            if(x > y){
                x -= y;
                // y *= 2;
                px = (px + pl * p0) % M;
                pl = pl * p1 % M;
            }else if(x < y){
                y -= x;
                // x *= 2;
                py = (py + pl * p1) % M;
                pl = pl * p0 % M;
            }else{
                px = (px + pl * p0) % M;
                py = (py + pl * p1) % M;
                break;
            }
        }while(make_pair(x, y) != T);

        cout << px << '\n';
    }

    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: