QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489716#6554. Endless RoadpandapythonerTL 1ms3836kbC++232.8kb2024-07-24 23:31:272024-07-24 23:31:27

Judging History

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

  • [2024-07-24 23:31:27]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3836kb
  • [2024-07-24 23:31: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 = 0; k < n; k += 1) {
            ll sum = 0;
            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;
                }
            }
            prob[k] = sum * 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: 3532kb

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

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

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

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

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

output:


result: