QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302357#5357. 芒果冰加了空气dayux5 81ms199876kbC++141.3kb2024-01-10 19:48:142024-01-10 19:48:14

Judging History

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

  • [2024-01-10 19:48:14]
  • 评测
  • 测评结果:5
  • 用时:81ms
  • 内存:199876kb
  • [2024-01-10 19:48:14]
  • 提交

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%