QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#753159 | #9120. Huge Segment Tree | cpismylifeOwO | RE | 1ms | 7820kb | C++23 | 1.5kb | 2024-11-16 11:35:09 | 2024-11-16 11:35:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int MaxN = 1e6 + 5;
int k;
void Inp()
{
cin >> k;
}
long long Pow2[MaxN];
long long Fact[MaxN];
long long RevFact[MaxN];
long long C(long long k, long long n)
{
if (k > n)
{
return 0;
}
return ((Fact[n] * RevFact[n - k]) % mod * RevFact[k]) % mod;
}
void Exc()
{
Pow2[0] = Fact[0] = 1;
for (int x = 1; x <= 3 * k; x++)
{
Pow2[x] = (Pow2[x - 1] * 2) % mod;
Fact[x] = (Fact[x - 1] * x) % mod;
}
RevFact[1] = 1;
for (int x = 2; x <= 3 * k; x++)
{
RevFact[x] = (mod - (mod / x) * RevFact[mod % x] % mod) % mod;
}
RevFact[0] = 1;
for (int x = 1; x <= 3 * k; x++)
{
RevFact[x] = (RevFact[x - 1] * RevFact[x]) % mod;
}
cout << Pow2[k + 1] - 1 << " ";
for (int x = 2; x <= 2 * k - 2; x++)
{
long long res = 0;
for (int y = 0; y < k; y++)
{
res = (res + Pow2[k - y - 1] * ((C(x, 2 * y) - 2 * C(x, y) % mod + 2 * C(x - 1, y)) % mod) % mod) % mod;
}
cout << (res % mod + mod) % mod << " ";
}
}
int main()
{
//freopen("D.INP", "r", stdin);
//freopen("D.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int w = 1; w <= test; w++)
{
Inp();
Exc();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7732kb
input:
2
output:
7 3
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 7804kb
input:
3
output:
15 14 6 1
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
4
output:
31 43 36 19 6 1
result:
ok 6 tokens
Test #4:
score: 0
Accepted
time: 1ms
memory: 7816kb
input:
5
output:
63 110 132 114 70 30 8 1
result:
ok 8 tokens
Test #5:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
6
output:
127 255 384 448 400 272 136 47 10 1
result:
ok 10 tokens
Test #6:
score: 0
Accepted
time: 1ms
memory: 7820kb
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: 1ms
memory: 7724kb
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: 1ms
memory: 7720kb
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: 1ms
memory: 7764kb
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: 1ms
memory: 7688kb
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