QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489749 | #6554. Endless Road | pandapythoner | WA | 1ms | 3824kb | C++23 | 4.7kb | 2024-07-25 00:13:29 | 2024-07-25 00:13:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
const ll inf = 1e18;
mt19937 rnd(234);
const ll mod = 998244353;
ll bin_pow(ll x, ll n) {
if (n == 0) {
return 1;
}
ll a = bin_pow(x, n / 2);
a = (a * a) % mod;
if (n & 1) {
a = (a * x) % mod;
}
return a;
}
ll inv(ll x) {
return bin_pow(x, mod - 2);
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a, b, c;
cin >> a >> b >> c;
ll n;
cin >> n;
int fsz = n + 100;
vector<ll> f(fsz + 1), invf(fsz + 1);
f[0] = invf[0] = 1;
for (int i = 1; i <= fsz; i += 1) {
f[i] = (f[i - 1] * i) % mod;
invf[i] = inv(f[i]);
}
auto cnk = [&](ll n, ll k) -> ll {
if (k < 0 or k > n) {
return 0;
}
return f[n] * invf[k] % mod * invf[n - k] % mod;
};
array<ll, 3> base = { a, b, c };
vector<ll> diff(n, 0);
auto make_flex = [&](const array<ll, 3>& v) -> vector<ll> {
vector<ll> prob(n, 0);
ll t = v[0] - v[1];
auto B = [&](ll x, ll y) -> ll {
return invf[x] * invf[x + t] % mod * invf[y] % mod;
};
for (ll k = abs(t); k < n; k += 1) {
ll sum = 0;
if (k >= abs(t) + 2) {
ll f = (k * k - t * t) % mod;
ll s1 = prob[k - 2];
ll s2 = prob[k - 2];
ll s3 = prob[k - 1];
ll val = (v[0] + v[1] + v[2] + k) / 3;
for (ll x = max({ 0ll, val - v[0] - 5 }); x <= val - v[0] + 5; x += 1) {
ll y = k - t - 2 * x;
if (v[0] + x == v[2] + y and x - 1 >= 0 and x - 1 + t >= 0) {
s1 = (s1 + B(x - 1, y)) % mod;
}
if (v[0] + x == v[2] + y - 1 or v[0] + x == v[2] + y - 2) {
if (y - 2 >= 0) {
s2 = (s2 + mod - B(x, y - 2)) % mod;
}
}
if (v[0] + x == v[2] + y - 1) {
if (y - 1 >= 0) {
s3 = (s3 + mod - B(x, y - 1)) % mod;
}
}
}
prob[k] = (4 * s1 + mod - s2 + (2 * k - 1) * s3) % mod * inv(f) % mod;
continue;
}
for (ll x = max(0ll, -t); 2 * x <= k - t; x += 1) {
ll y = k - t - 2 * x;
if (v[0] + x >= v[2] + y) {
sum = (sum + B(x, y)) % mod;
if (k >= abs(t) + 2) {
ll f = (k * k - t * t) % mod;
ll s1 = 0, s2 = 0, s3 = 0;
if (x - 1 >= 0) {
s1 = 4 * B(x - 1, y) % mod;
}
if (y - 2 >= 0) {
s2 = (mod - B(x, y - 2)) % mod;
}
if (y - 1 >= 0) {
s3 = (2 * k - 1) * B(x, y - 1) % mod;
}
assert(B(x, y) == inv(f) * (s1 + s2 + s3) % mod);
}
}
}
prob[k] = sum;
}
for (ll k = 0; k < n; k += 1) {
prob[k] = prob[k] * f[k] % mod * inv(bin_pow(3, k)) % mod;
}
return prob;
};
for (ll k = 0; k < n; k += 1) {
diff[k] = 1;
if ((a + b + c + k) % 3 == 0) {
ll val = (a + b + c + k) / 3;
ll x = val - a, y = val - b, z = val - c;
if (x >= 0 and y >= 0 and z >= 0) {
ll prob = f[k] * invf[x] % mod * invf[y] % mod * invf[z] % mod * inv(bin_pow(3, k)) % mod;
diff[k] = (diff[k] + mod - prob) % mod;
}
}
}
vector<int> p = { 0, 1, 2 };
for (int i = 0; i < 3; i += 1) {
for (int j = i + 1; j < 3; j += 1) {
int k = 3 - i - j;
auto probs = make_flex({ base[i], base[j], base[k] });
for (int k = 0; k < n; k += 1) {
diff[k] = (diff[k] + probs[k]) % mod;
}
}
}
ll expectation = max({ a, b, c });
ll inv3 = inv(3);
for (int k = 1; k <= n; k += 1) {
expectation = (expectation + diff[k - 1] * inv3) % mod;
cout << expectation << "\n";
}
return 0;
}
/*
0 0 0
5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3756kb
input:
0 0 0 5
output:
1 332748119 554580198 813384290 110916042
result:
ok 5 number(s): "1 332748119 554580198 813384290 110916042"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
111 222 456 10
output:
332748574 665496692 457 332748575 665496693 458 332748576 665496694 459 332748577
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
0 0 0 100
output:
1 332748119 554580198 813384290 110916042 714792256 290298773 430883712 974509238 873989993 734317944 835462688 154757268 923205242 885314705 209291025 637685124 643859336 487195910 506723497 772211975 340846245 868174491 606646848 450657563 475687624 419817368 824343170 19675432 120063916 342859234...
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
0 1 2 100
output:
332748120 110916042 887328317 665496239 743548267 288929440 817492294 724529743 614222297 317076859 988811171 967076519 751471247 133606165 14748157 362021315 549489057 937277754 415597831 485073323 916155749 240424973 413728850 410208012 903519447 196084907 817848817 766168642 161891353 619301293 7...
result:
ok 100 numbers
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3808kb
input:
1 13 99 400
output:
332748217 665496335 100 332748218 665496336 101 332748219 665496337 102 332748220 665496338 103 332748221 665496339 104 332748222 992210733 631027860 605526472 358647663 814514690 300626513 190471839 710456022 37766735 740578618 360847883 921054245 72614584 972554350 558051499 545533779 829936329 93...
result:
wrong answer 17th numbers differ - expected: '665496340', found: '992210733'