QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489715 | #6554. Endless Road | pandapythoner | WA | 0ms | 3832kb | C++23 | 2.8kb | 2024-07-24 23:29:50 | 2024-07-24 23:29:51 |
Judging History
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 - 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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
0 0 0 5
output:
1 332748119 554580198 813384290 110916042
result:
ok 5 number(s): "1 332748119 554580198 813384290 110916042"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3832kb
input:
111 222 456 10
output:
332748574 665496692 457 332748575 665496693 458 332748576 665496694 446405121 121878519
result:
wrong answer 9th numbers differ - expected: '459', found: '446405121'