QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#581473 | #9376. Game | Jasper_H | WA | 64ms | 3632kb | C++17 | 2.0kb | 2024-09-22 12:57:12 | 2024-09-22 12:57:12 |
Judging History
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'