QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88880#5357. 芒果冰加了空气Scintilla0 184ms137892kbC++141.7kb2023-03-17 20:26:202023-03-17 20:26:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-17 20:26:21]
  • 评测
  • 测评结果:0
  • 用时:184ms
  • 内存:137892kb
  • [2023-03-17 20:26:20]
  • 提交

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%