QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617507#4811. Be CarefulLeheRE 1ms7696kbC++141.7kb2024-10-06 15:56:272024-10-06 15:56:28

Judging History

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

  • [2024-10-06 15:56:28]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7696kb
  • [2024-10-06 15:56:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define sec second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define pb push_back
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
int n,ans[210],dp[210][210],deg[210],pd[210];
vector<int>g[210];
int c[1LL<<18],pc[1LL<<18];
void out(int u)
{
	cout<<"u="<<u<<":";
	for(int i=0;i<=n;i++)cout<<dp[u][i]<<" ";
	cout<<endl;
}
void dfs(int u,int f)
{
	for(auto v:g[u])
		if(v!=f)
		{
			deg[u]++;
			dfs(v,u);
		}
	if(!deg[u])for(int i=0;i<=n;i++)dp[u][i]=1;
	else
	{
		int m=deg[u];
//		memset(c,0,sizeof(c));
		for(int i=(1LL<<m)-1;i>0;i--)c[i]=0;
		c[0]=1;
		for(auto v:g[u])
		{
			if(v==f)continue;
			memset(pd,0,sizeof(pd));
			for(int i=0;i<=n;i++)(pd[min(i,m)]+=dp[v][i])%=mod;
			for(int i=(1LL<<m)-1;i>=0;i--)pc[i]=c[i],c[i]=0;
			for(int i=(1LL<<m)-1;i>=0;i--)
				for(int j=0;j<=m;j++)
					(c[j==m?i:(i|(1LL<<j))]+=pc[i]*pd[j]%mod)%=mod;
//			cout<<"!v="<<v<<endl;
//			cout<<" --- "<<u<<" "<<m<<endl;
//			for(int i=0;i<(1LL<<m);i++)cout<<"    ---    "<<i<<" "<<c[i]<<endl;
					
		}
//		cout<<"  "<<u<<" "<<m<<endl;
//		for(int i=0;i<(1LL<<m);i++)cout<<"        "<<i<<" "<<c[i]<<endl;
		for(int i=0;i<(1LL<<m);i++)
		{
			int mex;
			for(int j=0;j<=m;j++)
				if(!(i&(1LL<<j)))
				{
					mex=j;
					break;
				}
			(dp[u][mex]+=c[i])%=mod;
		}
	}
//	out(u);
}

signed main()
{
//	freopen("mex.in","r",stdin);
//	freopen("mex.out","w",stdout);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1,0);
	for(int i=0;i<=n;i++)cout<<dp[1][i]<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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

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

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

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

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

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

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

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

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

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

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: -100
Runtime Error

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:


result: