QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489749#6554. Endless RoadpandapythonerWA 1ms3824kbC++234.7kb2024-07-25 00:13:292024-07-25 00:13:30

Judging History

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

  • [2024-07-25 00:13:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2024-07-25 00:13:29]
  • 提交

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'