QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88880 | #5357. 芒果冰加了空气 | Scintilla | 0 | 184ms | 137892kb | C++14 | 1.7kb | 2023-03-17 20:26:20 | 2023-03-17 20:26:21 |
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;
g[sz[v] + 1] = 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: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 2ms
memory: 3844kb
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: -5
Wrong Answer
time: 3ms
memory: 3808kb
input:
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 8 10
output:
951190844
result:
wrong answer 1st lines differ - expected: '64804', found: '951190844'
Subtask #2:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 184ms
memory: 137892kb
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
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%