QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #350298 | #8010. Hierarchies of Judges | ucup-team004# | AC ✓ | 5909ms | 18368kb | C++20 | 6.7kb | 2024-03-10 16:55:08 | 2024-03-10 16:55:09 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
int power(int a, int b) {
int res = 1;
for (; b; b /= 2, a = 1LL * a * a % P) {
if (b % 2) {
res = 1LL * res * a % P;
}
}
return res;
}
std::vector<int> rev, roots {0, 1};
void dft(std::vector<int> &a) {
int n = a.size();
if (int(rev.size()) != n) {
int k = __builtin_ctz(n) - 1;
rev.resize(n);
for (int i = 0; i < n; i++) {
rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
}
}
for (int i = 0; i < n; i++) {
if (rev[i] < i) {
std::swap(a[i], a[rev[i]]);
}
}
if (roots.size() < n) {
int k = __builtin_ctz(roots.size());
roots.resize(n);
while ((1 << k) < n) {
int e = power(31, 1 << (__builtin_ctz(P - 1) - k - 1));
for (int i = 1 << (k - 1); i < (1 << k); i++) {
roots[2 * i] = roots[i];
roots[2 * i + 1] = 1LL * roots[i] * e % P;
}
k++;
}
}
for (int k = 1; k < n; k *= 2) {
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; j++) {
int u = a[i + j];
int v = 1LL * a[i + j + k] * roots[k + j] % P;
a[i + j] = (u + v) % P;
a[i + j + k] = (u - v) % P;
}
}
}
}
void idft(std::vector<int> &a) {
int n = a.size();
std::reverse(a.begin() + 1, a.end());
dft(a);
int inv = (1 - P) / n;
for (int i = 0; i < n; i++) {
a[i] = 1LL * a[i] * inv % P;
}
}
std::vector<int> mul(std::vector<int> a, std::vector<int> b) {
int n = 1, tot = a.size() + b.size() - 1;
while (n < tot) {
n *= 2;
}
if (tot < 128) {
std::vector<int> c(a.size() + b.size() - 1);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % P;
}
}
return c;
}
a.resize(n);
b.resize(n);
dft(a);
dft(b);
for (int i = 0; i < n; i++) {
a[i] = 1LL * a[i] * b[i] % P;
}
idft(a);
a.resize(tot);
return a;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> fac(n + 1), invfac(n + 1), inv(n + 1);
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = 1LL * fac[i - 1] * i % P;
}
invfac[n] = power(fac[n], P - 2);
for (int i = n; i; i--) {
inv[i] = 1LL * invfac[i] * fac[i - 1] % P;
invfac[i - 1] = 1LL * invfac[i] * i % P;
}
std::vector<int> f(n + 1), g(n + 1), seqg(n + 1), ef(n + 1), efg(n + 1), g2efg(n + 1), fg(n + 1), gefg(n + 1);
// for (int i = 1; i <= n; i++) {
// for (int j = 0; j < i; j++) {
// f[i] = (f[i] + 1LL * (ef[j] - g2efg[j]) * seqg[i - j - 1]) % P;
// }
// for (int j = 0; j < i; j++) {
// g[i] = (g[i] + 1LL * (ef[j] - efg[j]) * seqg[i - j - 1]) % P;
// }
// for (int j = 0; j < i; j++) {
// ef[i] = (ef[i] + 1LL * ef[j] * f[i - j] % P * (i - j)) % P;
// }
// ef[i] = 1LL * ef[i] * inv[i] % P;
// for (int j = 0; j < i; j++) {
// fg[i] = (fg[i] + 1LL * f[j] * g[i - j]) % P;
// }
// for (int j = 0; j < i; j++) {
// efg[i] = (efg[i] + 1LL * efg[j] * fg[i - j] % P * (i - j)) % P;
// }
// efg[i] = 1LL * efg[i] * inv[i] % P;
// for (int j = 0; j < i; j++) {
// g2efg[i] = (g2efg[i] + 1LL * gefg[j] * g[i - j]) % P;
// }
// for (int j = 0; j < i; j++) {
// gefg[i] = (gefg[i] + 1LL * efg[j] * g[i - j]) % P;
// }
// for (int j = 0; j < i; j++) {
// seqg[i] = (seqg[i] + 1LL * seqg[j] * g[i - j]) % P;
// }
// }
seqg[0] = 1;
ef[0] = 1;
efg[0] = 1;
auto work = [&](auto self, int l, int r) -> void {
if (r - l == 1) {
if (l > 0) {
ef[l] = 1LL * ef[l] * inv[l] % P;
efg[l] = 1LL * efg[l] * inv[l] % P;
}
return;
}
int m = (l + r + 1) / 2;
// int m = r - 1;
self(self, l, m);
auto at = [](auto &f, int offset = 0) {
return [&, offset](int i) { return i + offset < 0 ? 0 : f[i + offset]; };
};
auto add = [&](auto &dst, auto f, auto g) {
if (l == 0) {
std::vector<int> a(m), b(m);
for (int i = 0; i < m; i++) {
a[i] = f(i);
b[i] = g(i);
}
std::vector<int> c = mul(a, b);
for (int i = m; i < r; i++) {
if (i - 1 < c.size()) {
dst[i] = (dst[i] + c[i - 1]) % P;
}
}
} else {
std::vector<int> a(m - l), b(r - l - 1);
for (int i = 0; i < m - l; i++) {
a[i] = f(l + i);
}
for (int i = 0; i < r - l - 1; i++) {
b[i] = g(i);
}
std::vector<int> c = mul(a, b);
for (int i = m; i < r; i++) {
if (i - l - 1 < c.size()) {
dst[i] = (dst[i] + c[i - l - 1]) % P;
}
}
for (int i = 0; i < m - l; i++) {
a[i] = g(l + i);
}
for (int i = 0; i < r - l - 1; i++) {
b[i] = f(i);
}
c = mul(a, b);
for (int i = m; i < r; i++) {
if (i - l - 1 < c.size()) {
dst[i] = (dst[i] + c[i - l - 1]) % P;
}
}
}
};
add(f, [&](int i) { return (ef[i] - g2efg[i]) % P; }, at(seqg));
add(g, [&](int i) { return (ef[i] - efg[i]) % P; }, at(seqg));
add(ef, at(ef), [&](int i) { return 1LL * (i + 1) * f[i + 1] % P; });
add(fg, at(f), at(g, 1));
add(efg, at(efg), [&](int i) { return 1LL * (i + 1) * fg[i + 1] % P; });
add(g2efg, at(gefg), at(g, 1));
add(gefg, at(efg), at(g, 1));
add(seqg, at(seqg), at(g, 1));
self(self, m, r);
};
work(work, 0, n + 1);
int ans = 1LL * (f[n] + g[n]) * fac[n] % P;
ans = (ans + P) % P;
std::cout << ans << "\n";
return 0;
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3816kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3
output:
24
result:
ok 1 number(s): "24"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5
output:
3190
result:
ok 1 number(s): "3190"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
100
output:
413875584
result:
ok 1 number(s): "413875584"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2
output:
4
result:
ok 1 number(s): "4"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3
output:
24
result:
ok 1 number(s): "24"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
4
output:
236
result:
ok 1 number(s): "236"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5
output:
3190
result:
ok 1 number(s): "3190"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
6
output:
55182
result:
ok 1 number(s): "55182"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
7
output:
1165220
result:
ok 1 number(s): "1165220"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
8
output:
29013896
result:
ok 1 number(s): "29013896"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
9
output:
832517514
result:
ok 1 number(s): "832517514"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
10
output:
96547079
result:
ok 1 number(s): "96547079"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
11
output:
296100513
result:
ok 1 number(s): "296100513"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
12
output:
672446962
result:
ok 1 number(s): "672446962"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
13
output:
986909297
result:
ok 1 number(s): "986909297"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
14
output:
306542229
result:
ok 1 number(s): "306542229"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
15
output:
8548107
result:
ok 1 number(s): "8548107"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
16
output:
773960239
result:
ok 1 number(s): "773960239"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
17
output:
611627547
result:
ok 1 number(s): "611627547"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
18
output:
91793980
result:
ok 1 number(s): "91793980"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
19
output:
689202618
result:
ok 1 number(s): "689202618"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
20
output:
605957782
result:
ok 1 number(s): "605957782"
Test #25:
score: 0
Accepted
time: 106ms
memory: 4388kb
input:
10000
output:
713782215
result:
ok 1 number(s): "713782215"
Test #26:
score: 0
Accepted
time: 245ms
memory: 4844kb
input:
20000
output:
337916836
result:
ok 1 number(s): "337916836"
Test #27:
score: 0
Accepted
time: 497ms
memory: 5260kb
input:
30000
output:
580803285
result:
ok 1 number(s): "580803285"
Test #28:
score: 0
Accepted
time: 576ms
memory: 6400kb
input:
40000
output:
732660392
result:
ok 1 number(s): "732660392"
Test #29:
score: 0
Accepted
time: 1119ms
memory: 7048kb
input:
50000
output:
660835595
result:
ok 1 number(s): "660835595"
Test #30:
score: 0
Accepted
time: 1146ms
memory: 7540kb
input:
60000
output:
323452070
result:
ok 1 number(s): "323452070"
Test #31:
score: 0
Accepted
time: 1276ms
memory: 9060kb
input:
70000
output:
307315915
result:
ok 1 number(s): "307315915"
Test #32:
score: 0
Accepted
time: 1315ms
memory: 9568kb
input:
80000
output:
951757567
result:
ok 1 number(s): "951757567"
Test #33:
score: 0
Accepted
time: 2552ms
memory: 10256kb
input:
90000
output:
426123208
result:
ok 1 number(s): "426123208"
Test #34:
score: 0
Accepted
time: 2600ms
memory: 10848kb
input:
100000
output:
827418228
result:
ok 1 number(s): "827418228"
Test #35:
score: 0
Accepted
time: 2610ms
memory: 11248kb
input:
110000
output:
541614559
result:
ok 1 number(s): "541614559"
Test #36:
score: 0
Accepted
time: 2661ms
memory: 11616kb
input:
120000
output:
184688986
result:
ok 1 number(s): "184688986"
Test #37:
score: 0
Accepted
time: 2665ms
memory: 12044kb
input:
130000
output:
898089371
result:
ok 1 number(s): "898089371"
Test #38:
score: 0
Accepted
time: 2906ms
memory: 14688kb
input:
140000
output:
949540221
result:
ok 1 number(s): "949540221"
Test #39:
score: 0
Accepted
time: 2936ms
memory: 15440kb
input:
150000
output:
767689851
result:
ok 1 number(s): "767689851"
Test #40:
score: 0
Accepted
time: 2991ms
memory: 15884kb
input:
160000
output:
553494563
result:
ok 1 number(s): "553494563"
Test #41:
score: 0
Accepted
time: 3021ms
memory: 16348kb
input:
170000
output:
270711750
result:
ok 1 number(s): "270711750"
Test #42:
score: 0
Accepted
time: 5817ms
memory: 17112kb
input:
180000
output:
108155689
result:
ok 1 number(s): "108155689"
Test #43:
score: 0
Accepted
time: 5855ms
memory: 17804kb
input:
190000
output:
327542856
result:
ok 1 number(s): "327542856"
Test #44:
score: 0
Accepted
time: 5909ms
memory: 18124kb
input:
200000
output:
236144151
result:
ok 1 number(s): "236144151"
Test #45:
score: 0
Accepted
time: 5897ms
memory: 18368kb
input:
198798
output:
16935264
result:
ok 1 number(s): "16935264"
Extra Test:
score: 0
Extra Test Passed