QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489772#6554. Endless RoadpandapythonerAC ✓3998ms65940kbC++234.8kb2024-07-25 00:33:272024-07-25 00:33:30

Judging History

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

  • [2024-07-25 00:33:30]
  • 评测
  • 测评结果:AC
  • 用时:3998ms
  • 内存:65940kb
  • [2024-07-25 00:33:27]
  • 提交

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 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: 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: 3616kb

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: 3628kb

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: 3656kb

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: 1ms
memory: 3636kb

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: 1ms
memory: 3636kb

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: 3572kb

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: 3987ms
memory: 65680kb

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: 3992ms
memory: 65588kb

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: 3971ms
memory: 65720kb

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: 3759ms
memory: 65732kb

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: 3432ms
memory: 65760kb

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: 3967ms
memory: 65724kb

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: 3987ms
memory: 65600kb

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: 3916ms
memory: 65580kb

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: 3540kb

input:

1000000 1000000 1000000
1

output:

1000001

result:

ok 1 number(s): "1000001"

Test #17:

score: 0
Accepted
time: 3985ms
memory: 65772kb

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: 3998ms
memory: 65756kb

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: 3973ms
memory: 65804kb

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: 3982ms
memory: 65732kb

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: 3968ms
memory: 65664kb

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: 3986ms
memory: 65672kb

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: 3974ms
memory: 65800kb

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: 3980ms
memory: 65824kb

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: 3980ms
memory: 65916kb

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: 3890ms
memory: 65916kb

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: 3544ms
memory: 65720kb

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: 3971ms
memory: 65940kb

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: 3983ms
memory: 65736kb

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: 3968ms
memory: 65752kb

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