QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581473#9376. GameJasper_HWA 64ms3632kbC++172.0kb2024-09-22 12:57:122024-09-22 12:57:12

Judging History

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

  • [2024-09-22 12:57:12]
  • 评测
  • 测评结果:WA
  • 用时:64ms
  • 内存:3632kb
  • [2024-09-22 12:57:12]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define eb emplace_back
#define rep(i, s, t) for (int i = (s);i <= (t);i++)
#define dep(i, t, s) for (int i = (t);i >= (s);i--)
#define For(i, n) for (int i = 0;i < (n);i++)
using namespace std;
using LL = long long;
using Pii = pair<int, int>;
const int N = 1e5 + 10, inf = 0x3f3f3f3f, P = 998244353;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
int x, y, a, b, c, p;
struct Mat {
    int a[3][3];
    Mat() { memset(a, 0, sizeof a); }
    void build() {
        rep(i, 0, 2) a[i][i] = 1;
    }
    int* operator[](int i) {
        return a[i];
    }
};
Mat operator * (Mat A, Mat B) {
    Mat res;
    rep(i, 1, 2) {
        rep(j, 1, 2) {
            rep(k, 1, 2) (res[i][j] += A[i][k] * B[k][j]) %= P;
        }
    }
    return res;
}
Mat qpow(Mat A, int b) {
    Mat res; res.build();
    while (b) {
        if (b & 1) res = res * A;
        A = A * A; b >>= 1;
    }
    return res;
}
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P; b >>= 1;
    }
    return res;
}
int f(int x, int y) {
    if (x == y) return p;
    if (x < y) {
        int k = (y - 1) / x; // 上取整
        return qpow(p, k) * f(x, y - k * x) % P;
    }
    if (x > y) {
        int k = (x - y) / y;
        if (k == 0) {
            return p + f(x - y, y);
        } else {
            Mat res;
            res[1][1] = 1 - p; res[1][2] = p;
            res[2][1] = 0; res[2][2] = 1;
            res = qpow(res, k);
            return (res[1][1] * f(x - k * y, y) % P + res[1][2] % P) % P;
        }
    }
}
void solve() {
    cin >> x >> y >> a >> b >> c;
    p = a * qpow(a + b, P - 2);
    int ans = f(x, y);
    ans = (ans % P + P) % P;
    cout << ans << '\n';
}
signed main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    cin.tie(0)->ios::sync_with_stdio(false);
    int T = 1;
    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: 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
Wrong Answer
time: 64ms
memory: 3632kb

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:

57660923
349699982
612621163
715857038
592200562
329686335
870227707
169499045
86138309
415694940
143218515
464905228
426243016
864656779
750317399
778225400
486881524
16020688
198191519
189360084
966510181
512645443
695650039
530346826
550002158
375091767
458326158
551455286
667870434
918218440
593...

result:

wrong answer 1st lines differ - expected: '947058399', found: '57660923'