QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#935913#10215. Gona Guni玩原神的都进队了 (Junlin Ye, Ruichen Dai, Chenghan Li)#AC ✓1322ms534740kbC++142.0kb2025-03-15 16:54:402025-03-15 16:54:46

Judging History

This is the latest submission verdict.

  • [2025-03-15 16:54:46]
  • Judged
  • Verdict: AC
  • Time: 1322ms
  • Memory: 534740kb
Show
  • [2025-03-15 16:54:40]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5,MOD=998244353,MAXM=205;
inline void add(int &x,const int &y) { if((x+=y)>=MOD) x-=MOD; }
inline void sub(int &x,const int &y) { if((x-=y)<0) x+=MOD; }
int n,m,f[MAXN][2][MAXM],rs[MAXM],S[MAXM][MAXM],fac[MAXM];
vector <int> G[MAXN];
int siz[MAXN],h[MAXM],tmp[MAXM];
void conv(int *a,int *b,int x,int y) {
	memset(h,0,sizeof(h));
	for(int i=0;i<=x;++i) for(int j=0;j<=y&&i+j<=m;++j) {
		h[i+j]=(h[i+j]+1ll*a[i]*b[j])%MOD;
	}
}
void dfs(int u,int fz) {
	memset(f[u],0,sizeof(f[u])),f[u][1][0]=1;
	siz[u]=1;
	for(int v:G[u]) if(v^fz) dfs(v,u);
	for(int v:G[u]) if(v^fz) {
		memset(tmp,0,sizeof(tmp));
		conv(f[u][0],f[v][0],siz[u],siz[v]);
		for(int i=0;i<=m;++i) add(tmp[i],h[i]);

		conv(f[u][0],f[v][1],siz[u],siz[v]);
		for(int i=0;i<=m;++i) {
			add(tmp[i],h[i]);
			add(tmp[i],f[u][0][i]);
		}

		conv(f[u][1],f[v][1],siz[u],siz[v]);
		for(int i=0;i<=m;++i) {
			add(tmp[i],h[i]);
			if(i>0) add(tmp[i],h[i-1]);
		}

		conv(f[u][1],f[v][0],siz[u],siz[v]);
		for(int i=0;i<=m;++i) add(f[u][1][i],h[i]);

		for(int i=0;i<=m;++i) f[u][0][i]=tmp[i];
		siz[u]=min(siz[u]+siz[v],m);

		for(int i=0;i<=m;++i) {
			sub(rs[i],f[v][0][i]);
			sub(rs[i],f[v][1][i]);
			if(i>0) sub(rs[i],f[v][1][i-1]);
		}
	}
	for(int i=0;i<=m;++i) {
		f[u][0][i]=f[u][0][i]*2%MOD;
		f[u][1][i]=f[u][1][i]*2%MOD;
		if(i==0) sub(f[u][1][i],1);
		add(rs[i],f[u][0][i]);
		add(rs[i],f[u][1][i]);
	}
}
void solve() {
	cin>>n>>m;
	for(int i=1;i<=n;++i) G[i].clear();
	for(int i=1,u,v;i<n;++i) {
		cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	}
	memset(rs,0,sizeof(rs));
	dfs(1,0);
	int ans=0;
	for(int i=0;i<=m;++i) ans=(ans+1ll*fac[i]*S[m][i]%MOD*rs[i])%MOD;
	cout<<ans<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for(int i=fac[0]=1;i<MAXM;++i) fac[i]=1ll*fac[i-1]*i%MOD;
	for(int i=0;i<MAXM;++i) {
		S[i][0]=!i;
		for(int j=1;j<=i;++j) S[i][j]=(S[i-1][j-1]+1ll*S[i-1][j]*j)%MOD;
	}
	int _; cin>>_;
	while(_--) solve();
	return 0;
}
源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 11976kb

input:

2
3 1
1 2
1 3
20 200
1 2
1 3
2 4
1 5
5 6
1 7
6 8
6 9
3 10
4 11
6 12
11 13
4 14
13 15
15 16
6 17
13 18
15 19
13 20

output:

4
286430678

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 976ms
memory: 505420kb

input:

1
300000 200
1 2
1 3
2 4
1 5
4 6
5 7
6 8
4 9
4 10
1 11
11 12
12 13
11 14
11 15
15 16
15 17
11 18
13 19
17 20
11 21
21 22
22 23
21 24
23 25
21 26
26 27
23 28
21 29
23 30
21 31
31 32
32 33
31 34
31 35
31 36
34 37
35 38
31 39
36 40
31 41
41 42
41 43
41 44
43 45
43 46
44 47
45 48
44 49
49 50
41 51
51 52...

output:

247999825

result:

ok single line: '247999825'

Test #3:

score: 0
Accepted
time: 388ms
memory: 12256kb

input:

3000
100 31
1 2
1 3
1 4
1 5
3 6
1 7
4 8
4 9
8 10
2 11
7 12
7 13
7 14
7 15
10 16
15 17
9 18
2 19
4 20
11 21
11 22
12 23
13 24
20 25
3 26
18 27
19 28
1 29
10 30
7 31
28 32
24 33
14 34
11 35
22 36
24 37
20 38
11 39
15 40
25 41
17 42
35 43
39 44
38 45
17 46
23 47
18 48
37 49
29 50
4 51
30 52
7 53
4 54
1...

output:

206703729
241517344
965256040
953191893
971103184
611763581
951769747
605254273
515657073
26158774
230121672
742384467
504292176
95015638
209242429
591984607
47728881
658540538
686302223
589359656
153765564
462000121
877695624
168867090
447225696
468677488
440776261
374615358
105981576
120340771
617...

result:

ok 3000 lines

Test #4:

score: 0
Accepted
time: 1061ms
memory: 502208kb

input:

1
300000 200
1 2
2 3
1 4
2 5
5 6
4 7
5 8
8 9
3 10
2 11
10 12
12 13
4 14
6 15
6 16
7 17
13 18
3 19
13 20
18 21
5 22
22 23
20 24
24 25
24 26
9 27
25 28
5 29
5 30
20 31
21 32
24 33
7 34
22 35
32 36
30 37
26 38
30 39
39 40
24 41
37 42
28 43
37 44
16 45
27 46
7 47
16 48
38 49
7 50
29 51
47 52
4 53
31 54
...

output:

634171363

result:

ok single line: '634171363'

Test #5:

score: 0
Accepted
time: 1303ms
memory: 534740kb

input:

1
300000 200
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 5...

output:

378891816

result:

ok single line: '378891816'

Test #6:

score: 0
Accepted
time: 934ms
memory: 501900kb

input:

1
300000 200
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
2...

output:

435358080

result:

ok single line: '435358080'

Test #7:

score: 0
Accepted
time: 1238ms
memory: 502428kb

input:

1
300000 200
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
...

output:

220992079

result:

ok single line: '220992079'

Test #8:

score: 0
Accepted
time: 1322ms
memory: 531232kb

input:

1
300000 200
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 5...

output:

872442796

result:

ok single line: '872442796'

Test #9:

score: 0
Accepted
time: 1139ms
memory: 518284kb

input:

1
300000 200
1 2
1 3
3 4
3 5
5 6
5 7
7 8
7 9
9 10
9 11
11 12
11 13
13 14
13 15
15 16
15 17
17 18
17 19
19 20
19 21
21 22
21 23
23 24
23 25
25 26
25 27
27 28
27 29
29 30
29 31
31 32
31 33
33 34
33 35
35 36
35 37
37 38
37 39
39 40
39 41
41 42
41 43
43 44
43 45
45 46
45 47
47 48
47 49
49 50
49 51
51 52...

output:

77589834

result:

ok single line: '77589834'

Test #10:

score: 0
Accepted
time: 1015ms
memory: 508812kb

input:

1
300000 200
1 2
1 3
2 4
1 5
1 6
6 7
6 8
8 9
9 10
6 11
11 12
11 13
13 14
11 15
11 16
16 17
17 18
17 19
18 20
16 21
21 22
22 23
22 24
24 25
21 26
26 27
26 28
26 29
27 30
26 31
31 32
31 33
33 34
31 35
31 36
36 37
37 38
36 39
39 40
36 41
41 42
42 43
42 44
44 45
41 46
46 47
46 48
46 49
48 50
46 51
51 52...

output:

137591617

result:

ok single line: '137591617'

Test #11:

score: 0
Accepted
time: 964ms
memory: 502124kb

input:

1
300000 200
1 2
1 3
2 4
1 5
4 6
5 7
6 8
4 9
4 10
3 11
8 12
1 13
7 14
8 15
14 16
7 17
7 18
16 19
3 20
12 21
13 22
9 23
13 24
18 25
10 26
11 27
12 28
13 29
15 30
22 31
23 32
8 33
4 34
16 35
13 36
24 37
6 38
27 39
7 40
39 41
37 42
10 43
37 44
40 45
9 46
16 47
7 48
24 49
34 50
45 51
46 52
43 53
53 54
5...

output:

529039223

result:

ok single line: '529039223'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2025-04-15 08:58:48 | 開源專案