QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489767#6554. Endless RoadpandapythonerRE 1ms3836kbC++234.8kb2024-07-25 00:30:462024-07-25 00:30:46

Judging History

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

  • [2024-07-25 00:30:46]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3836kb
  • [2024-07-25 00:30:46]
  • 提交

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) {
                            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: 1ms
memory: 3828kb

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

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: -100
Runtime Error

input:

0 1 2
100

output:


result: