QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549897 | #9120. Huge Segment Tree | ucup-team1766 | RE | 6ms | 11636kb | C++17 | 2.2kb | 2024-09-06 23:13:14 | 2024-09-06 23:13:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
const int MAXN = 500005;
long long fact[MAXN];
long long inv_fact[MAXN];
long long binpow(long long a, long long b) {
if (b == 0) {
return 1;
}
long long c = binpow(a, b / 2);
if (b % 2 == 0) {
return c * c % MOD;
} else {
return c * c % MOD * a % MOD;
}
}
long long modinv(long long a) {
return binpow(a, MOD - 2);
}
long long nck(int n, int k) {
if (k > n) {
return 0;
}
return fact[n] * inv_fact[n - k] % MOD * inv_fact[k] % MOD;
}
vector<long long> divide(vector<long long> &p, vector<long long> &q) {
vector<long long> res(p.size());
for (int i = p.size() - 1; i >= q.size() - 1; i--) {
int pow_diff = i - q.size() + 1;
long long mult_diff = p[i] * modinv(q[q.size() - 1]) % MOD;
res[pow_diff] = mult_diff;
for (int j = 0; j < q.size(); j++) {
p[j + pow_diff] -= q[j] * mult_diff % MOD;
p[j + pow_diff] = (p[j + pow_diff] + MOD) % MOD;
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
fact[0] = 1;
for (int i = 1; i < MAXN; i++) {
fact[i] = fact[i - 1] * i % MOD;
}
inv_fact[MAXN - 1] = modinv(fact[MAXN - 1]);
for (int i = MAXN - 2; i >= 0; i--) {
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}
int K;
cin >> K;
vector<long long> p1(K + 2);
for (int i = 0; i <= K; i++) {
p1[i] = 2 * nck(K, i) % MOD;
}
p1[0] = (p1[0] - binpow(2, K + 1) + MOD) % MOD;
vector<long long> p2(2 * K + 1);
for (int i = 0; i <= 2 * K; i++) {
p2[i] = MOD - nck(2 * K, i);
}
p2[0] = (p2[0] + binpow(2, K)) % MOD;
vector<long long> den {1, MOD - 2, MOD - 1};
vector<long long> quo = divide(p2, den);
vector<long long> res(2 * K - 1);
res[0] = binpow(2, K) - 1;
res[1] = 1;
for (int i = 1; i <= 2 * K - 2; i++) {
res[i] += quo[i];
if (i <= K + 1) {
res[i] += p1[i];
}
res[i] %= MOD;
cout << res[i] << " ";
}
cout << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11344kb
input:
2
output:
7 3
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 6ms
memory: 11328kb
input:
3
output:
15 14 6 1
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 6ms
memory: 11592kb
input:
4
output:
31 43 36 19 6 1
result:
ok 6 tokens
Test #4:
score: 0
Accepted
time: 6ms
memory: 11340kb
input:
5
output:
63 110 132 114 70 30 8 1
result:
ok 8 tokens
Test #5:
score: 0
Accepted
time: 6ms
memory: 11348kb
input:
6
output:
127 255 384 448 400 272 136 47 10 1
result:
ok 10 tokens
Test #6:
score: 0
Accepted
time: 3ms
memory: 11636kb
input:
7
output:
255 558 978 1401 1610 1478 1066 589 240 68 12 1
result:
ok 12 tokens
Test #7:
score: 0
Accepted
time: 0ms
memory: 11332kb
input:
8
output:
511 1179 2292 3803 5250 5987 5576 4183 2482 1137 388 93 14 1
result:
ok 14 tokens
Test #8:
score: 0
Accepted
time: 3ms
memory: 11364kb
input:
9
output:
1023 2438 5088 9398 14896 20038 22632 21250 16406 10282 5144 2006 588 122 16 1
result:
ok 16 tokens
Test #9:
score: 0
Accepted
time: 3ms
memory: 11428kb
input:
10
output:
2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1
result:
ok 18 tokens
Test #10:
score: 0
Accepted
time: 3ms
memory: 11292kb
input:
11
output:
4095 10070 22782 48209 92140 156292 232068 298744 330926 313422 252186 171122 97008 45368 17200 5155 1176 192 20 1
result:
ok 20 tokens
Test #11:
score: -100
Runtime Error
input:
500000