QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88881 | #5357. 芒果冰加了空气 | Scintilla | 5 | 149ms | 137980kb | C++14 | 1.7kb | 2023-03-17 20:27:23 | 2023-03-17 20:27:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
const int P = 998244353;
const int N = 5e3 + 10;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }
int n, C[N][N], f[N][N], g[N], o[N], sz[N], ans;
vector <int> e[N];
void dfs(int u, int fa) {
sz[u] = 1, f[u][1] = 1;
for (int v : e[u]) if (v != fa) {
dfs(v, u);
rep(i, 1, sz[u]) o[i] = f[u][i], f[u][i] = 0;
rep(i, 1, n) g[i] = 0;
drep(i, sz[v], 0) g[i] = inc(g[i + 1], f[v][i]);
rep(i, 1, sz[u] + sz[v]) rep(j, 1, min(i, sz[u])) {
f[u][i] = inc(f[u][i], mul(mul(C[i - 1][j - 1], o[j]), g[i - j]));
}
sz[u] += sz[v];
}
}
int main() {
n = read();
rep(i, 1, n - 1) {
int u = read(), v = read();
e[u].emplace_back(v);
e[v].emplace_back(u);
}
rep(i, 0, n) C[i][0] = 1;
rep(i, 1, n) rep(j, 1, i) C[i][j] = inc(C[i - 1][j], C[i - 1][j - 1]);
dfs(1, 0);
rep(i, 1, n) ans = inc(ans, f[1][i]);
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 3696kb
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: 3692kb
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: 0ms
memory: 3700kb
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: 3696kb
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: 3700kb
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: 3704kb
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: 2ms
memory: 3600kb
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: 2ms
memory: 3808kb
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: 3696kb
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: 2ms
memory: 3572kb
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: 2ms
memory: 3700kb
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: 0ms
memory: 3808kb
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: 3ms
memory: 3556kb
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: 0ms
memory: 3792kb
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: 2ms
memory: 3824kb
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: 3ms
memory: 3792kb
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: 3644kb
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: 3640kb
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: 3648kb
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: 2ms
memory: 3684kb
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: 0ms
memory: 3664kb
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: 3ms
memory: 3668kb
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: 3636kb
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: 2ms
memory: 3648kb
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: 3592kb
input:
3 1 2 2 3
output:
5
result:
ok single line: '5'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3704kb
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: 149ms
memory: 137980kb
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: 3688kb
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%