QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#76815 | #5357. 芒果冰加了空气 | iye | 5 | 120ms | 102448kb | C++17 | 1.3kb | 2023-02-12 11:44:25 | 2023-02-12 11:44:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
const int N = 5005, mo = 998244353;
int ksm(int x, int y) {
int sum = 1;
for(; y; y >>= 1, x = (ll)x * x % mo)
if(y & 1) sum = (ll)sum * x % mo;
return sum;
}
int n;
vector<int> e[N];
int f[N][N], siz[N];
int h[N];
int fac[N * 2], ifac[N * 2];
int binom(int x, int y) {
return (ll)fac[x] * ifac[y] % mo * ifac[x - y] % mo;
}
void dfs(int x, int from) {
for(int y : e[x]) if(y != from) dfs(y, x);
memset(f[x], 0, sizeof(f[x]));
f[x][1] = 1;
int sz = 1;
for(int y : e[x]) if(y != from) {
memset(h, 0, sizeof(h));
fo(a, 1, sz) {
int sum = 0;
fd(b, siz[y], 0) {
(sum += f[y][b]) %= mo;
(h[a + b] += (ll)f[x][a] * sum % mo * binom(a - 1 + b, b) % mo) %= mo;
}
}
sz += siz[y];
fo(a, 1, sz) f[x][a] = h[a];
}
siz[x] = sz;
return;
}
int main() {
fac[0] = 1;
fo(i, 1, 10000) fac[i] = (ll)fac[i - 1] * i % mo;
ifac[10000] = ksm(fac[10000], mo - 2);
fd(i, 10000, 1) ifac[i - 1] = (ll)ifac[i] * i % mo;
scanf("%d", &n);
fo(i, 1, n - 1) {
int u, v;
scanf("%d %d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
int ans = 0;
fo(i, 1, n) (ans += f[1][i]) %= mo;
printf("%d\n", ans);
return 0;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 4184kb
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: 2ms
memory: 3960kb
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: 2ms
memory: 3916kb
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: 2ms
memory: 3996kb
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: 2ms
memory: 4160kb
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: 2ms
memory: 3972kb
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: 3916kb
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: 0ms
memory: 3988kb
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: 3ms
memory: 5964kb
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: 0ms
memory: 4176kb
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: 6000kb
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: 2ms
memory: 3968kb
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: 2ms
memory: 3956kb
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: 2ms
memory: 3924kb
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: 5976kb
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: 0ms
memory: 3864kb
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: 2ms
memory: 3864kb
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: 2ms
memory: 3868kb
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: 2ms
memory: 4112kb
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: 0ms
memory: 3920kb
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: 2ms
memory: 3956kb
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: 2ms
memory: 3948kb
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: 2ms
memory: 3972kb
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: 0ms
memory: 3988kb
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: 3ms
memory: 3848kb
input:
3 1 2 2 3
output:
5
result:
ok single line: '5'
Test #26:
score: 0
Accepted
time: 2ms
memory: 4000kb
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: 120ms
memory: 102448kb
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: 2ms
memory: 4376kb
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%