QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489769 | #6554. Endless Road | pandapythoner | TL | 15ms | 3824kb | C++23 | 4.8kb | 2024-07-25 00:31:58 | 2024-07-25 00:31:58 |
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, -t, val - v[0] - 10 }); x <= val - v[0] + 10; x += 1) {
ll y = k - t - 2 * x;
if ((v[0] + x >= v[2] + y and x >= -t) and v[0] + x - 1 < v[2] + y) {
if (x - 1 >= 0 and x - 1 + t >= 0) {
s1 = (s1 + B(x - 1, y)) % mod;
}
}
if (v[0] + x < v[2] + y and 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 and 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 and x + t - 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
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 3788kb
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: 3824kb
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: 3588kb
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: 0
Accepted
time: 9ms
memory: 3508kb
input:
1 13 99 400
output:
332748217 665496335 100 332748218 665496336 101 332748219 665496337 102 332748220 665496338 103 332748221 665496339 104 332748222 665496340 105 332748223 665496341 106 332748224 665496342 107 332748225 665496343 108 332748226 665496344 109 332748227 665496345 110 332748228 665496346 111 332748229 66...
result:
ok 400 numbers
Test #6:
score: 0
Accepted
time: 15ms
memory: 3620kb
input:
0 5 61 500
output:
332748179 665496297 62 332748180 665496298 63 332748181 665496299 64 332748182 665496300 65 332748183 665496301 66 332748184 665496302 67 332748185 665496303 68 332748186 665496304 69 332748187 665496305 70 332748188 665496306 71 332748189 665496307 72 332748190 665496308 73 332748191 665496309 74 3...
result:
ok 500 numbers
Test #7:
score: 0
Accepted
time: 15ms
memory: 3812kb
input:
0 2 5 500
output:
332748123 665496241 6 160212063 928408335 510761521 966293238 563709096 935610018 527751405 306730784 675447864 43719138 618247863 449591825 439345742 162772460 991789358 686798696 770662249 804237354 797676708 831486461 184129352 546170122 749993280 900200261 972640212 246249281 413426795 136984414...
result:
ok 500 numbers
Test #8:
score: -100
Time Limit Exceeded
input:
1 10 27 2000000