QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#406530#4811. Be CarefullexiyvvWA 1ms7812kbC++175.2kb2024-05-07 13:24:532024-05-07 13:24:54

Judging History

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

  • [2024-05-07 13:24:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7812kb
  • [2024-05-07 13:24:53]
  • 提交

answer

#pragma GCC optimize(3)
//#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#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];
int L[(1<<20)+5],r[(1<<20)+5];
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();});
	int tmp=0;
	for(auto y:v[x]){
		if(y==l)continue;
		if(lf[y]){
			continue;
		}
		int cnt=0;
        for(int j=0;j<=n;j++){
        	if(dp[y][j]!=0)cnt++;
		}
		tmp=max(tmp,cnt);
    }
//    cout<<x<<":"<<tmp<<endl;
    if(tmp<=20){
    	L[0]=1;
    	for(auto y:v[x]){
			if(y==l)continue;
			if(lf[y]){
				continue;
			}
    		for(int j=0;j<n;j++){
    			if(dp[y][j]!=0){
    				for(int i=0;i<(1<<tmp);i++)
   					(r[i|(1<<j)]+=L[i]*dp[y][j])%=mod;
				}
			}
			for(int i=0;i<(1<<tmp);i++)
			L[i]=r[i],r[i]=0;
		}
		for(int i=0;i<(1<<tmp);i++){
			int a=i,w=L[i];
//			cout<<a<<' '<<w<<endl;
			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++;
			}
		}
		return ;
	}
    for(auto y:v[x]){
		if(y==l)continue;
		if(lf[y]){
			continue;
		}
		g.clear();
        int cnt=0;
		for(int j=0;j<=n;j++)
			if(dp[y][j]!=0){
                cnt++;
				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;
//            if(x==1)cout<<cnt<<endl;
		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;
		}
	}
//vector<int>a;
	for(int i=1;i<n;i++){
		cin>>p1>>p2;
//		if(i>159)
//		a.push_back(p1),a.push_back(p2);
		v[p1].push_back(p2);
		v[p2].push_back(p1);
	}
	dfs(1,0);
//	if(dp[1][0]==193649645){
//		for(int i=0;i<a.size();i+=2)
//		cout<<a[i]<<' '<<a[i+1]<<endl;
//		return 0;
//	}
	for(int i=0;i<=n;i++)
	cout<<dp[1][i]<<endl;
	return 0;
}

詳細信息

Test #1:

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

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

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

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

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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

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

input:

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

output:

76009161
613174968
231680949
371606079
462267469
29375574
306720677
749077361
0
0
0

result:

wrong answer 1st numbers differ - expected: '10', found: '76009161'