QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#564876#4811. Be CarefulHarry27182WA 1ms10068kbC++143.2kb2024-09-15 16:27:082024-09-15 16:27:08

Judging History

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

  • [2024-09-15 16:27:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10068kb
  • [2024-09-15 16:27:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
vector<int>e[205],e1[205],e2[205];
int f[100005],g[100005][205],tmp[100005][205],tmp2[100005][205],tmp3[100005];
int dp[205][205],n,suf[205][205],C[205][205],pw[205][205],u,v;
const int mod=998244353;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void dfs(int u,int fa)
{
	if(e[u].size()==1&&fa)return;
	int num=0,B=0,mn=0x3f3f3f3f,mx=0;vector<int>vec;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa)continue;
		dfs(v,u);
		if(e[v].size()==1)num++;
		else vec.emplace_back(e[v].size()),mx=max(mx,(int)e[v].size());
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<=vec.size();i++)
	{
		if((i==0?0:vec[i-1])+vec.size()-i+(i>10)<=mn)
		{
			mn=(i==0?0:vec[i-1])+vec.size()-i;
			B=(i==0?0:vec[i-1]);
		}
	}
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa)continue;
		if(e[v].size()==1);
		else if(e[v].size()<=B)e1[u].emplace_back(v);
		else e2[u].emplace_back(v);
	}
	assert((1<<B)<=100000&&(1<<e2[u].size())<=100000);
	for(int i=0;i<(1<<B);i++)f[i]=0;
	f[0]=1;
	for(int i=0;i<e1[u].size();i++)
	{
		int v=e1[u][i];
		for(int s=0;s<(1<<B);s++)tmp3[s]=f[s],f[s]=0;
		for(int s=0;s<(1<<B);s++)
		{
			if(!tmp[s])continue;
			for(int j=0;j<B;j++)Add(f[s|(1<<j)],1ll*tmp3[s]*dp[v][j]%mod);
		}
	}
	for(int t=0;t<(1<<B);t++)
	{
		if(!f[t])continue;
		for(int s=0;s<(1<<e2[u].size());s++)for(int j=0;j<=num;j++)g[s][j]=0;
		g[0][0]=1;
		for(int i=0;i<=n;i++)
		{
			for(int s=0;s<(1<<e2[u].size());s++)
			{
				for(int j=0;j<=num;j++)
				{
					if(!g[s][j])continue;
					if(i<B&&((t>>i)&1))continue;
					int now=1ll*f[t]*g[s][j]%mod;
					for(int j=0;j<e2[u].size();j++)if(!((s>>j)&1))now=1ll*now*suf[e2[u][j]][i+1]%mod;
					Add(dp[u][i],1ll*now*pw[n-i][num-j]%mod);
				}
			}
			for(int s=0;s<(1<<e2[u].size());s++)
			{
				for(int j=0;j<=num;j++)tmp[s][j]=g[s][j];
			}
			for(int j=0;j<e2[u].size();j++)
			{
				for(int s=0;s<(1<<e2[u].size());s++)
				{
					if((s>>j)&1)continue;
					for(int k=0;k<=num;k++)
					{
						if(!g[s][k])continue;
						Add(g[s|(1<<j)][k],1ll*g[s][k]*dp[e2[u][j]][i]%mod);
					}
				}
			}
			for(int s=0;s<(1<<e2[u].size());s++)
			{
				for(int j=0;j<=num;j++)tmp2[s][j]=g[s][j],g[s][j]=0;
				for(int j=0;j<=num;j++)
				{
					if(!tmp2[s][j])continue;
					for(int k=j;k<=num;k++)Add(g[s][k],1ll*tmp2[s][j]*C[num-j][k-j]%mod);
				}
			}
			if(i>=B&&!((t>>i)&1))
			{
				for(int s=0;s<(1<<e2[u].size());s++)
				{
					for(int j=0;j<=num;j++)Add(g[s][j],mod-tmp[s][j]);
				}
			}
		}
	}
	for(int i=n;i>=0;i--)
	{
		suf[u][i]=suf[u][i+1];
		Add(suf[u][i],dp[u][i]);
	}
	//for(int i=0;i<=n;i++)cout<<u<<' '<<i<<' '<<dp[u][i]<<'\n';
}
int main()
{
	//freopen("mex.in","r",stdin);
	//freopen("mex.out","w",stdout);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<n;i++)cin>>u>>v,e[u].emplace_back(v),e[v].emplace_back(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%mod;
	}
	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]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	dfs(1,0); 
	for(int i=0;i<=n;i++)cout<<dp[1][i]<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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

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

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

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

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

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: -100
Wrong Answer
time: 0ms
memory: 7836kb

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
398102720
369524547
579799809
404617965
15600991
959138046
628411891
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 3rd numbers differ - expected: '277265229', found: '398102720'