QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#406619#4811. Be CarefulBronyaRE 9ms9916kbC++143.1kb2024-05-07 15:18:022024-05-07 15:18:17

Judging History

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

  • [2024-05-07 15:18:17]
  • 评测
  • 测评结果:RE
  • 用时:9ms
  • 内存:9916kb
  • [2024-05-07 15:18:02]
  • 提交

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<<15],sav[1<<15];
int dp[1<<15][205],dp2[1<<15][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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 6108kb

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: 6100kb

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: 5848kb

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: 9916kb

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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: 6096kb

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: 8096kb

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: 8136kb

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: 6100kb

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: 1ms
memory: 6148kb

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: 5876kb

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: 0ms
memory: 8008kb

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: 1ms
memory: 6156kb

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: 5920kb

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: 1ms
memory: 5916kb

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: 9ms
memory: 6132kb

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: