QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#406620#4811. Be CarefulBronyaRE 6ms10244kbC++143.1kb2024-05-07 15:19:032024-05-07 15:19:03

Judging History

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

  • [2024-05-07 15:19:03]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:10244kb
  • [2024-05-07 15:19:03]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
int f[205][205],lim[205],suf[205][205];
int n;
struct edge{
	int obj;
	int last;
}e[405];
int head[205],g;
void link(int u,int v){
	e[++g].obj=v;
	e[g].last=head[u];
	head[u]=g;
}
bool pd[205];
void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].last){
		int v=e[i].obj;
		if(v==fa)continue;
		dfs(v,u);pd[u]=true;
	}
}
const int B=15,mo=998244353;
int add(int u,int v){
	return (u+v>=mo?u+v-mo:u+v);
}
int f2[1<<19],sav[1<<19];
int dp[1<<19][205],dp2[1<<19][205];
int pw[205][205];
int C[205][205];
void Solve(vector<int>son1,vector<int>son2,int hav,int x){
	int ma=0;lim[x]=son1.size()+son2.size()+hav;
	for(auto v:son1)ma=max(ma,lim[v]);
	f2[0]=1;ma++;
	for(auto v:son1){
		for(int i=0;i<(1<<ma);i++){
			for(int j=0;j<ma;j++)
				sav[i|(1<<j)]=add(sav[i|(1<<j)],f2[i]*1ll*f[v][j]%mo);
		}
		for(int i=0;i<(1<<ma);i++)f2[i]=sav[i],sav[i]=0;
	}
	int m=son2.size();
	for(int i=0;i<(1<<ma);i++){
		if(!f2[i])continue;
		for(int s=0;s<(1<<m);s++)
			for(int k=0;k<=hav;k++)
				dp[s][k]=dp2[s][k]=0;
		dp[0][0]=1;
		for(int j=0;j<=lim[x];j++){
			if(j<ma&&(i&(1<<j))){
				for(int s=0;s<(1<<m);s++)
					for(int k=0;k<=hav;k++)
						dp2[s][k]=dp[s][k],dp[s][k]=0;
			}
			for(int s=0;s<(1<<m);s++)
				for(int k=0;k<=hav;k++){
					int S=(((1<<m)-1)^s),mor=pw[n-j][hav-k];
					if(!dp[s][k])continue;
					while(S){
						int l=__lg(S);
						mor=1ll*mor*suf[son2[l]][j+1]%mo;
						S^=(1<<l);
					}
					f[x][j]=add(f[x][j],1ll*mor*dp[s][k]%mo*1ll*f2[i]%mo);
				}
			for(int l=0;l<m;l++){
				for(int s=0;s<(1<<m);s++){
					if(s&(1<<l))continue;
					for(int k=0;k<=hav;k++)
						dp2[s|(1<<l)][k]=add(dp2[s|(1<<l)][k],1ll*add(dp[s][k],dp2[s][k])*f[son2[l]][j]%mo);
				}
			}
			for(int s=0;s<(1<<m);s++)
				for(int k=hav;k>=0;k--)
					for(int l=0;l<k;l++){
						dp2[s][k]=add(dp2[s][k],1ll*add(dp[s][l],dp2[s][l])*C[hav-l][k-l]%mo);
					}
			for(int s=0;s<(1<<m);s++)
				for(int k=0;k<=hav;k++)
					dp[s][k]=dp2[s][k],dp2[s][k]=0;
		}
		f2[i]=0;
	}
}
bool cmp(int x,int y){
	return lim[x]<lim[y];
}
void dfs2(int u,int fa){
	vector<int>son;
	int hav=0;
	for(int i=head[u];i;i=e[i].last){
		int v=e[i].obj;
		if(v==fa)continue;
		if(!pd[v])hav++;
		else {
			dfs2(v,u);
			son.push_back(v);
		}
	}
	sort(son.begin(),son.end(),cmp);
	vector<int>son1,son2;
	int mi=1e9,fj=0;
	for(int i=0;i<son.size();i++){
		int v=son[i];
		if(lim[v]+son.size()-i-1<mi)
			mi=lim[v]+son.size()-i-1,fj=i;
	}
	for(int i=0;i<son.size();i++)
		if(i<=fj)son1.push_back(son[i]);
		else son2.push_back(son[i]);
	Solve(son1,son2,hav,u);
	for(int i=n;i>=0;i--)suf[u][i]=add(suf[u][i+1],f[u][i]);

}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		link(u,v);link(v,u);
	}
	for(int i=0;i<=n;i++){
		pw[i][0]=1;
		for(int j=1;j<=n;j++)pw[i][j]=1ll*pw[i][j-1]*i%mo;
	}
	C[0][0]=1;
	for(int i=1;i<=n;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=add(C[i-1][j-1],C[i-1][j]);
	}
	dfs(1,0);
	dfs2(1,0);
	for(int i=0;i<=n;i++)printf("%d\n",f[1][i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2
1 3
2 4
2 5

output:

55
127
34
0
0
0

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 9928kb

input:

8
1 2
1 3
1 4
1 5
1 6
6 7
6 8

output:

69632
265534
133905
47790
12636
1944
0
0
0

result:

ok 9 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 8136kb

input:

3
1 2
2 3

output:

1
3
0
0

result:

ok 4 number(s): "1 3 0 0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 8144kb

input:

2
1 2

output:

2
1
0

result:

ok 3 number(s): "2 1 0"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7864kb

input:

10
1 8
1 9
6 1
2 1
1 4
1 10
1 5
7 1
3 1

output:

1755647
612579511
359376750
200038110
104287680
49974120
21379680
7771680
2177280
362880
0

result:

ok 11 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 9948kb

input:

10
2 8
2 9
6 2
2 1
2 4
2 10
2 5
7 2
3 2

output:

114358881
100000000
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 9948kb

input:

10
7 8
8 9
6 5
2 1
3 4
9 10
4 5
7 6
3 2

output:

10
1
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 7876kb

input:

10
3 6
2 4
4 9
8 4
2 5
10 5
3 7
2 1
1 3

output:

27510
31142
102399
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 9880kb

input:

14
10 3
6 2
2 8
3 13
1 3
1 2
3 14
4 2
9 3
12 3
2 5
7 2
11 3

output:

930962871
780146137
253920328
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 9960kb

input:

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

output:

572808214
694156482
763085092
958730326
465749894
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 21 numbers

Test #11:

score: 0
Accepted
time: 1ms
memory: 9972kb

input:

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

output:

778184256
242901486
277265229
855621813
564317020
918444623
408876720
314039448
593931360
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 22 numbers

Test #12:

score: 0
Accepted
time: 1ms
memory: 8200kb

input:

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

output:

142157709
5878180
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 23 numbers

Test #13:

score: 0
Accepted
time: 0ms
memory: 7988kb

input:

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

output:

7619809
175546557
7936610
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 24 numbers

Test #14:

score: 0
Accepted
time: 1ms
memory: 7968kb

input:

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

output:

24
576
15025
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 7952kb

input:

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

output:

24
7962624
236177977
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #16:

score: 0
Accepted
time: 6ms
memory: 10244kb

input:

200
1 199
95 1
1 75
177 1
66 1
157 1
85 1
1 193
1 26
8 1
38 1
151 1
1 56
63 1
1 138
1 59
190 1
1 36
1 120
156 1
115 1
1 118
171 1
6 1
113 1
20 1
83 1
1 176
33 1
153 1
1 169
22 1
1 159
1 27
87 1
1 129
1 44
174 1
1 93
77 1
1 122
1 125
1 23
1 81
112 1
173 1
1 51
32 1
96 1
184 1
116 1
67 1
1 94
1 104
19...

output:

211917199
369375874
201944418
582671162
183066248
639389350
952947539
137147613
216366713
398936459
73236543
354059031
727857197
121548413
610762100
573534011
706945631
286154195
226699593
267771858
823273748
233587424
176942776
226493975
707601105
339075191
694353149
944734662
932707579
934386415
4...

result:

ok 201 numbers

Test #17:

score: -100
Runtime Error

input:

200
2 199
95 2
2 75
177 2
66 2
157 2
85 2
2 193
2 26
8 2
38 2
151 2
2 56
63 2
2 138
2 59
190 2
2 36
2 120
156 2
115 2
2 118
171 2
6 2
113 2
20 2
83 2
2 176
33 2
153 2
2 169
22 2
2 159
2 27
87 2
2 129
2 44
174 2
2 93
77 2
2 122
2 125
2 23
2 81
112 2
173 2
2 51
32 2
96 2
184 2
116 2
67 2
2 94
2 104
19...

output:


result: