QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#406550#4811. Be CarefullexiyvvRE 0ms0kbC++173.5kb2024-05-07 13:46:382024-05-07 13:46:38

Judging History

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

  • [2024-05-07 13:46:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-07 13:46:38]
  • 提交

answer

#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];
#define LIM 23
int L[(1<<LIM)+5],r[(1<<LIM)+5],G0[(1<<LIM)+5],G2[(1<<LIM)+5],vis[(1<<LIM)+5];
unordered_map<int,int>mp;
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);
	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=j+1;
		}
		tmp=max(tmp,cnt);
    }
    if(tmp<=LIM){
    	for(int i=0;i<(1<<tmp);i++)L[i]=0;
    	L[0]=1;
    	int tmp2=0;
			int T=0,T2=0;
			G0[++T]=0;
    	for(auto y:v[x]){
			if(y==l)continue;
			if(lf[y]){
				continue;
			}
			int cnt=0;
			T2=0;
    				for(int I=1;I<=T;I++)vis[G0[I]]=0;
    		for(int j=0;j<n;j++){
    			if(dp[y][j]!=0){
    				cnt=j+1;
    				for(int I=1;I<=T;I++){
    					int i=G0[I];
    					if(!vis[i|(1<<j)])vis[i|(1<<j)]=1,G2[++T2]=(i|(1<<j));
	   					(r[i|(1<<j)]+=L[i]*dp[y][j])%=mod;
	   				}
				}
			}
			for(int i=1;i<=T2;i++)
			G0[i]=G2[i];
			T=T2;
			tmp2=max(tmp2,cnt);
			for(int i=0;i<(1<<tmp2);i++)
			L[i]=r[i],r[i]=0;
		}
		for(int I=1;I<=T;I++){
			int i=G0[I];
			vis[i]=0;
			int a=i,w=L[i];
			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;
		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;
}

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

5
1 2
1 3
2 4
2 5

output:


result: