QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#406481#4811. Be CarefullexiyvvWA 1ms3760kbC++142.4kb2024-05-07 12:50:252024-05-07 12:50:25

Judging History

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

  • [2024-05-07 12:50:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3760kb
  • [2024-05-07 12:50:25]
  • 提交

answer

#pragma GCC optimize("-Ofast", "-finline", "-funroll-loops", "-fno-stack-protector")
#include <bits/stdc++.h>
#define int long long
//#define __int128 int
using namespace std;
const int mod=998244353;
int n,p1,p2,dp[205][205],lf[205];
int qpow[205][205],f[205],g[205],C[205][205],q[205][205];
__int128 fm2[205];
vector<int>v[205];
#define R 1
int F[205][(1<<R)+5],G[205][(1<<R)+5],t[205];
unordered_map<int,int>mp;
//const int mod2=1000000000000009;
void dfs(int x,int l){
	int tg=0,cnt2=0;
	for(auto y:v[x])
		if(y!=l)dfs(y,x),tg=1,cnt2++;
	if(!tg){
		lf[x]=1;
		return ;
	}
	vector<pair<__int128,int> >f,g;
	f.push_back({0,1});
	int cnt=0;
	int lim=cnt2+1;
	for(auto y:v[x]){
		if(y==l)continue;
		if(lf[y]){
			cnt++;
			continue;
		}
	}
	lim=min(lim,(int)(sqrt((n-cnt)*2)+0.1)+cnt);
//	if(x==1)return ;
//	if(n>150)lim=min(lim,27ll);
	sort(v[x].begin(),v[x].end(),[&](int x,int y){return v[x].size()<v[y].size();});
	for(auto y:v[x]){
		if(y==l)continue;
		if(lf[y]){
			continue;
		}
		g.clear();
		for(int j=0;j<=n/2+1;j++)
			if(dp[y][j]!=0)
				for(auto i:f)
				g.push_back({i.first|fm2[min(j,lim)],i.second*dp[y][j]%mod});
		for(auto i:g)(mp[i.first]+=i.second)%=mod;
		f.clear();
		for(auto i:g){
			int r=mp[i.first];
			if(r)f.push_back({i.first,r}),mp[i.first]=0;
		}
	}
	for(auto i:f){
		int a=i.first,w=i.second;
		int c=0;
		for(int j=0;j<=n;j++){
			if(!(a&fm2[j]))
			(dp[x][j]+=w*q[j-c][cnt])%=mod;
			else c++;
		}
	}
}
int p[205];
signed main(){
//	freopen("tree.in","r",stdin);
//	freopen("tree.out","w",stdout);
	cin>>n;
	fm2[0]=1;
	for(int i=1;i<=n/2+1;i++)fm2[i]=fm2[i-1]*2;
	f[0]=1;
	for(int i=0;i<=n;i++){
		int mul=1;
		for(int j=0;j<=n;j++){
			qpow[i][j]=mul;
			(mul*=i)%=mod;
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(j==0||j==i)C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	for(int j=0;j<=n;j++){
		for(int k=0;j+k<=n;k++)
		(q[0][j+k]+=f[j]*qpow[n][k]%mod*C[j+k][k])%=mod;
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=1;j+k<=n;k++)
			(g[j+k]+=f[j]*C[j+k][k])%=mod;
		}
		memcpy(f,g,sizeof(f));memset(g,0,sizeof(g));
		for(int j=0;j<=n;j++){
			for(int k=0;j+k<=n;k++)
			(q[i+1][j+k]+=f[j]*qpow[n-i-1][k]%mod*C[j+k][k])%=mod;
		}
	}
	for(int i=1;i<n;i++){
		cin>>p1>>p2;
		v[p1].push_back(p2);
		v[p2].push_back(p1);
	}
	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: 3760kb

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

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

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

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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

input:

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

output:

114056481
100000000
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st numbers differ - expected: '114358881', found: '114056481'