QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76815#5357. 芒果冰加了空气iye5 120ms102448kbC++171.3kb2023-02-12 11:44:252023-02-12 11:44:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-12 11:44:27]
  • 评测
  • 测评结果:5
  • 用时:120ms
  • 内存:102448kb
  • [2023-02-12 11:44:25]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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%