QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#302357 | #5357. 芒果冰加了空气 | dayux | 5 | 81ms | 199876kb | C++14 | 1.3kb | 2024-01-10 19:48:14 | 2024-01-10 19:48:14 |
Judging History
answer
#include <bits/stdc++.h>
const int maxn = 5e3, mod = 998244353;
std::array<int, maxn + 1> siz, tmpf;
std::array<std::array<int, maxn + 1>, maxn + 1> binom, f;
std::array<std::vector<int>, maxn + 1> g;
void dfs(int x, int fa) {
f[x][siz[x] = 1] = 1;
for (int v : g[x])
if (v != fa) {
dfs(v, x);
std::fill_n(tmpf.data() + 1, siz[x] + siz[v], 0);
for (int i = 1; i <= siz[x]; ++i)
for (int j = 0; j <= siz[v]; ++j)
tmpf[i + j] = (tmpf[i + j] + (long long)f[x][i] * f[v][j] % mod * binom[i - 1 + j][i - 1]) % mod;
std::copy_n(tmpf.data() + 1, siz[x] += siz[v], f[x].data() + 1);
}
for (int i = siz[x] - 1; i >= 0; --i)
f[x][i] = (f[x][i] + f[x][i + 1]) % mod;
}
int main() {
#ifndef ONLINE_JUDGE
std::freopen("QOJ5357.in", "r", stdin);
std::freopen("QOJ5357.out", "w", stdout);
#endif
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
for (int i = 1, u, v; i < n; ++i) {
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i <= n; ++i) {
binom[i][0] = binom[i][i] = 1;
for (int j = 1; j < i; ++j)
binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod;
}
dfs(1, 0);
std::cout << f[1][0] << std::endl;
return 0;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 5924kb
input:
10 1 2 2 3 3 4 5 4 6 4 7 4 8 4 9 4 10 4
output:
310862
result:
ok single line: '310862'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7888kb
input:
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 8 10
output:
64804
result:
ok single line: '64804'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7916kb
input:
10 1 2 1 3 3 4 3 5 3 6 4 7 3 8 4 9 4 10
output:
258182
result:
ok single line: '258182'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
output:
16796
result:
ok single line: '16796'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7884kb
input:
10 1 2 2 3 3 4 4 5 1 6 2 7 3 8 4 9 5 10
output:
78384
result:
ok single line: '78384'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5896kb
input:
10 1 2 1 3 2 4 3 5 2 6 4 7 3 8 7 9 9 10
output:
38896
result:
ok single line: '38896'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7840kb
input:
10 1 2 2 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3
output:
609656
result:
ok single line: '609656'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 9 10
output:
64804
result:
ok single line: '64804'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5872kb
input:
10 1 2 1 3 3 4 3 5 1 6 4 7 1 8 4 9 9 10
output:
118638
result:
ok single line: '118638'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 8 10
output:
22438
result:
ok single line: '22438'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7940kb
input:
10 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10
output:
16796
result:
ok single line: '16796'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5800kb
input:
10 1 2 1 3 1 4 3 5 4 6 2 7 3 8 5 9 5 10
output:
82316
result:
ok single line: '82316'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
8 1 2 3 2 4 2 5 2 6 2 7 2 8 2
output:
13700
result:
ok single line: '13700'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5852kb
input:
8 1 2 1 3 2 4 2 5 3 6 3 7 3 8
output:
3996
result:
ok single line: '3996'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5776kb
input:
8 1 2 2 3 1 4 1 5 1 6 3 7 6 8
output:
3490
result:
ok single line: '3490'
Test #16:
score: 0
Accepted
time: 1ms
memory: 7720kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8
output:
1430
result:
ok single line: '1430'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
8 1 2 1 3 2 4 3 5 4 6 5 7 6 8
output:
1430
result:
ok single line: '1430'
Test #18:
score: 0
Accepted
time: 1ms
memory: 7860kb
input:
8 1 2 2 3 3 4 2 5 3 6 5 7 4 8
output:
3232
result:
ok single line: '3232'
Test #19:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
8 1 2 2 3 4 3 5 3 6 3 7 3 8 3
output:
8970
result:
ok single line: '8970'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5776kb
input:
8 1 2 1 3 2 4 2 5 3 6 3 7 2 8
output:
3996
result:
ok single line: '3996'
Test #21:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
8 1 2 1 3 1 4 4 5 3 6 4 7 2 8
output:
3332
result:
ok single line: '3332'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 2 8
output:
1870
result:
ok single line: '1870'
Test #23:
score: 0
Accepted
time: 1ms
memory: 7824kb
input:
8 1 2 2 3 1 4 2 5 3 6 4 7 5 8
output:
2416
result:
ok single line: '2416'
Test #24:
score: 0
Accepted
time: 1ms
memory: 7960kb
input:
8 1 2 1 3 2 4 3 5 2 6 6 7 3 8
output:
2802
result:
ok single line: '2802'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
3 1 2 2 3
output:
5
result:
ok single line: '5'
Test #26:
score: 0
Accepted
time: 1ms
memory: 5872kb
input:
10 1 2 1 3 1 4 4 5 1 6 6 7 3 8 5 9 2 10
output:
78904
result:
ok single line: '78904'
Subtask #2:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 81ms
memory: 199876kb
input:
5000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
302039569
result:
wrong answer 1st lines differ - expected: '138172849', found: '302039569'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #37:
score: 0
Wrong Answer
time: 1ms
memory: 5820kb
input:
20 1 2 2 3 3 4 1 5 3 6 5 7 5 8 8 9 7 10 10 11 9 12 12 13 10 14 11 15 13 16 16 17 17 18 18 19 16 20
output:
555866770
result:
wrong answer 1st lines differ - expected: '85351498', found: '555866770'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%