QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489714#6554. Endless RoadpandapythonerRE 0ms0kbC++232.8kb2024-07-24 23:28:442024-07-24 23:28:44

Judging History

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

  • [2024-07-24 23:28:44]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-24 23:28:44]
  • 提交

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 = 0; 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 - k - 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: 0
Runtime Error

input:

0 0 0
5

output:


result: