QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489774 | #6554. Endless Road | pandapythoner | AC ✓ | 3904ms | 65936kb | C++23 | 4.8kb | 2024-07-25 00:34:41 | 2024-07-25 00:34:43 |
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] - 3 }); x <= val - v[0] + 3 and 2 * x <= k - t; 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
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 3828kb
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: 0ms
memory: 3836kb
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: 3792kb
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: 0ms
memory: 3840kb
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: 0ms
memory: 3848kb
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: 1ms
memory: 3552kb
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: 0
Accepted
time: 3896ms
memory: 65816kb
input:
1 10 27 2000000
output:
332748145 665496263 28 332748146 665496264 29 332748147 665496265 30 332748148 665496266 31 332748149 665496267 32 332748150 665496268 179663022 592144721 59304515 413053926 598971324 468557114 87778038 628766814 661124777 49657764 822965780 808952900 131374221 542991233 872933331 856066802 52510600...
result:
ok 2000000 numbers
Test #9:
score: 0
Accepted
time: 3887ms
memory: 65736kb
input:
1 2 3 2000000
output:
332748121 110916043 887328318 665496240 743548268 288929441 817492295 724529744 614222298 317076860 988811172 967076520 751471248 133606166 14748158 362021316 549489058 937277755 415597832 485073324 916155750 240424974 413728851 410208013 903519448 196084908 817848818 766168643 161891354 619301294 7...
result:
ok 2000000 numbers
Test #10:
score: 0
Accepted
time: 3863ms
memory: 65916kb
input:
0 100 19999 2000000
output:
332768117 665516235 20000 332768118 665516236 20001 332768119 665516237 20002 332768120 665516238 20003 332768121 665516239 20004 332768122 665516240 20005 332768123 665516241 20006 332768124 665516242 20007 332768125 665516243 20008 332768126 665516244 20009 332768127 665516245 20010 332768128 6655...
result:
ok 2000000 numbers
Test #11:
score: 0
Accepted
time: 3703ms
memory: 65640kb
input:
0 100000 299998 2000000
output:
333048116 665796234 299999 333048117 665796235 300000 333048118 665796236 300001 333048119 665796237 300002 333048120 665796238 300003 333048121 665796239 300004 333048122 665796240 300005 333048123 665796241 300006 333048124 665796242 300007 333048125 665796243 300008 333048126 665796244 300009 333...
result:
ok 2000000 numbers
Test #12:
score: 0
Accepted
time: 3386ms
memory: 65724kb
input:
0 700000 855555 2000000
output:
333603673 666351791 855556 333603674 666351792 855557 333603675 666351793 855558 333603676 666351794 855559 333603677 666351795 855560 333603678 666351796 855561 333603679 666351797 855562 333603680 666351798 855563 333603681 666351799 855564 333603682 666351800 855565 333603683 666351801 855566 333...
result:
ok 2000000 numbers
Test #13:
score: 0
Accepted
time: 3883ms
memory: 65736kb
input:
0 0 0 2000000
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 2000000 numbers
Test #14:
score: 0
Accepted
time: 3890ms
memory: 65920kb
input:
2 3 4 2000000
output:
332748122 110916044 887328319 665496241 743548269 288929442 817492296 724529745 614222299 317076861 988811173 967076521 751471249 133606167 14748159 362021317 549489059 937277756 415597833 485073325 916155751 240424975 413728852 410208014 903519449 196084909 817848819 766168644 161891355 619301295 7...
result:
ok 2000000 numbers
Test #15:
score: 0
Accepted
time: 3821ms
memory: 65684kb
input:
345 354 66876 2000000
output:
332814994 665563112 66877 332814995 665563113 66878 332814996 665563114 66879 332814997 665563115 66880 332814998 665563116 66881 332814999 665563117 66882 332815000 665563118 66883 332815001 665563119 66884 332815002 665563120 66885 332815003 665563121 66886 332815004 665563122 66887 332815005 6655...
result:
ok 2000000 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1000000 1000000 1000000 1
output:
1000001
result:
ok 1 number(s): "1000001"
Test #17:
score: 0
Accepted
time: 3894ms
memory: 65696kb
input:
1000000 1000000 1000000 2000000
output:
1000001 333748119 555580198 814384290 111916042 715792256 291298773 431883712 975509238 874989993 735317944 836462688 155757268 924205242 886314705 210291025 638685124 644859336 488195910 507723497 773211975 341846245 869174491 607646848 451657563 476687624 420817368 825343170 20675432 121063916 343...
result:
ok 2000000 numbers
Test #18:
score: 0
Accepted
time: 3902ms
memory: 65880kb
input:
0 5 6 2000000
output:
332748124 110916046 406692151 702468256 780520284 250588097 843966085 610875040 398881879 821245288 621559226 425057006 951494168 106603724 930151818 666086103 667717791 350655865 481819602 529636032 637307962 743456630 143921565 567351443 549064337 466547256 540711177 465397395 270202471 535482159 ...
result:
ok 2000000 numbers
Test #19:
score: 0
Accepted
time: 3885ms
memory: 65792kb
input:
0 5 7 2000000
output:
332748125 665496243 480636178 295776113 718900263 143780060 566904210 256978323 212246752 432709497 135090709 233560650 54196704 111597692 566089347 313956471 668686862 806073857 978650601 832909616 695025006 679208872 170965965 84033989 392810853 263850953 529617947 508523990 390319873 893015819 11...
result:
ok 2000000 numbers
Test #20:
score: 0
Accepted
time: 3864ms
memory: 65720kb
input:
0 5 78 2000000
output:
332748196 665496314 79 332748197 665496315 80 332748198 665496316 81 332748199 665496317 82 332748200 665496318 83 332748201 665496319 84 332748202 665496320 85 332748203 665496321 86 332748204 665496322 87 332748205 665496323 88 332748206 665496324 89 332748207 665496325 90 332748208 665496326 91 3...
result:
ok 2000000 numbers
Test #21:
score: 0
Accepted
time: 3876ms
memory: 65736kb
input:
0 5 89 2000000
output:
332748207 665496325 90 332748208 665496326 91 332748209 665496327 92 332748210 665496328 93 332748211 665496329 94 332748212 665496330 95 332748213 665496331 96 332748214 665496332 97 332748215 665496333 98 332748216 665496334 99 332748217 665496335 100 332748218 665496336 101 332748219 665496337 10...
result:
ok 2000000 numbers
Test #22:
score: 0
Accepted
time: 3886ms
memory: 65736kb
input:
0 13 14 2000000
output:
332748132 110916054 406692159 702468264 780520292 250588105 110916056 829359866 617366705 681116802 948953989 234481060 229537183 992883705 3601765 198689084 86597949 666462415 882234461 826340534 577804891 360593551 881941231 451339878 411498169 258507277 548025960 241201304 807539500 422744226 627...
result:
ok 2000000 numbers
Test #23:
score: 0
Accepted
time: 3893ms
memory: 65752kb
input:
0 13 81 2000000
output:
332748199 665496317 82 332748200 665496318 83 332748201 665496319 84 332748202 665496320 85 332748203 665496321 86 332748204 665496322 87 332748205 665496323 88 332748206 665496324 89 332748207 665496325 90 332748208 665496326 91 332748209 665496327 92 332748210 665496328 93 332748211 665496329 94 3...
result:
ok 2000000 numbers
Test #24:
score: 0
Accepted
time: 3889ms
memory: 65732kb
input:
12 45 100 2000000
output:
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 665496347 112 332748230 66...
result:
ok 2000000 numbers
Test #25:
score: 0
Accepted
time: 3904ms
memory: 65612kb
input:
12 45 1006 2000000
output:
332749124 665497242 1007 332749125 665497243 1008 332749126 665497244 1009 332749127 665497245 1010 332749128 665497246 1011 332749129 665497247 1012 332749130 665497248 1013 332749131 665497249 1014 332749132 665497250 1015 332749133 665497251 1016 332749134 665497252 1017 332749135 665497253 1018 ...
result:
ok 2000000 numbers
Test #26:
score: 0
Accepted
time: 3816ms
memory: 65692kb
input:
12 45 100654 2000000
output:
332848772 665596890 100655 332848773 665596891 100656 332848774 665596892 100657 332848775 665596893 100658 332848776 665596894 100659 332848777 665596895 100660 332848778 665596896 100661 332848779 665596897 100662 332848780 665596898 100663 332848781 665596899 100664 332848782 665596900 100665 332...
result:
ok 2000000 numbers
Test #27:
score: 0
Accepted
time: 3511ms
memory: 65724kb
input:
12 45 509999 2000000
output:
333258117 666006235 510000 333258118 666006236 510001 333258119 666006237 510002 333258120 666006238 510003 333258121 666006239 510004 333258122 666006240 510005 333258123 666006241 510006 333258124 666006242 510007 333258125 666006243 510008 333258126 666006244 510009 333258127 666006245 510010 333...
result:
ok 2000000 numbers
Test #28:
score: 0
Accepted
time: 3894ms
memory: 65884kb
input:
123 435 10340 2000000
output:
332758458 665506576 10341 332758459 665506577 10342 332758460 665506578 10343 332758461 665506579 10344 332758462 665506580 10345 332758463 665506581 10346 332758464 665506582 10347 332758465 665506583 10348 332758466 665506584 10349 332758467 665506585 10350 332758468 665506586 10351 332758469 6655...
result:
ok 2000000 numbers
Test #29:
score: 0
Accepted
time: 3887ms
memory: 65936kb
input:
12 45 1002 2000000
output:
332749120 665497238 1003 332749121 665497239 1004 332749122 665497240 1005 332749123 665497241 1006 332749124 665497242 1007 332749125 665497243 1008 332749126 665497244 1009 332749127 665497245 1010 332749128 665497246 1011 332749129 665497247 1012 332749130 665497248 1013 332749131 665497249 1014 ...
result:
ok 2000000 numbers
Test #30:
score: 0
Accepted
time: 3877ms
memory: 65652kb
input:
12 45 10012 2000000
output:
332758130 665506248 10013 332758131 665506249 10014 332758132 665506250 10015 332758133 665506251 10016 332758134 665506252 10017 332758135 665506253 10018 332758136 665506254 10019 332758137 665506255 10020 332758138 665506256 10021 332758139 665506257 10022 332758140 665506258 10023 332758141 6655...
result:
ok 2000000 numbers