QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#489766 | #6554. Endless Road | pandapythoner | RE | 1ms | 3760kb | C++23 | 4.8kb | 2024-07-25 00:29:56 | 2024-07-25 00:29:57 |
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 = 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] - 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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
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: 3604kb
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: 3616kb
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