QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#74479#4811. Be CarefulAppleblue17WA 4ms37320kbC++143.5kb2023-02-01 22:41:132023-02-01 22:41:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-01 22:41:14]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:37320kb
  • [2023-02-01 22:41:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=205,M=1e6+5,mod=998244353;
int n;
int mul[N],inv[N],S2[N][N],pre[N][N][N];
vector <int> G[N];
int ksm(int a,int x){
	int tot=1;
	while(x){
		if(x & 1ll) tot=1ll*tot*a%mod;
		a=1ll*a*a%mod;
		x>>=1ll;
	}
	return tot;
}
void gmod(int &x){
	x%=mod;
}
void init(int lim){
	mul[0]=inv[0]=1;
	for(int i=1;i<=lim;i++) mul[i]=1ll*mul[i-1]*i%mod;
	inv[lim]=ksm(mul[lim],mod-2);
	for(int i=lim-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	
	S2[0][0]=1;
	for(int i=1;i<=lim;i++){
		for(int j=1;j<=i;j++){
			S2[i][j]=(S2[i-1][j-1]+1ll*S2[i-1][j]*j%mod)%mod;
		}
	}
	
//	for(int c=0;c<=lim;c++){
//		for(int p=0;p<=c;p++){
//			for(int i=0;i<=c;i++)
//				gmod(pre[c][p]+=1ll*inv[c-i]%mod*inv[i]%mod*S2[i][p]%mod*ksm(n-t,c-i)%mod);
//		}
//	}
}

int cal(int c,int p,int x){
	if(pre[c][p][x]!=-1) return pre[c][p][x];
	int tot=0;
	for(int i=0;i<=c;i++)
		gmod(tot+=1ll*inv[c-i]%mod*inv[i]%mod*S2[i][p]%mod*ksm(x,c-i)%mod);
	return pre[c][p][x]=1ll*tot*mul[c]%mod*mul[p]%mod;
}

int dp[N][N],sdp[N][N];

int f[2][M],fid;
int g[2][M][N],gid;


void dfs(int u,int fa){
	vector <int> A,B;
	bool fl=0;
	for(int v: G[u]){
		if(v==fa) continue;
		fl=1;
		dfs(v,u);
	}
	
	if(!fl){
		for(int i=0;i<=n;i++) dp[u][i]=1;
		return ;
	}
	
	int mn=1e9,k;
	for(int t=0;t<=n;t++){
		int s=0;
		for(int v: G[u]){
			if(v==fa || G[v].size()==1) continue;
			s+=((int)G[v].size()-1>=t);
		}
		if(s<t && t+s<=mn) mn=t+s,k=t;
	}
	
	int c=0;
	for(int v: G[u]){
		if(v==fa) continue;
		if(G[v].size()==1) c++;
		else if((int)G[v].size()-1<k) A.push_back(v);
		else B.push_back(v);
	}
	
	fid=0;
	for(int mac=0;mac<(1<<k);mac++) f[fid][mac]=0;
	f[fid][0]=1;
	
	for(int i=0;i<(int)A.size();i++){
		int v=A[i];
		fid^=1;
		for(int mac=0;mac<(1<<k);mac++) f[fid][mac]=0;
		
		for(int mac=0;mac<(1<<k);mac++){
			for(int t=0;t<k;t++){
				gmod(f[fid][mac | (1<<t)]+=1ll*f[fid^1][mac]*dp[v][t]%mod);
			}
		}
	}
	
	
	if(u==1){
		cout<<"";
	}
	int m=A.size()+B.size()+c,l=B.size();
	for(int mac0=0;mac0<(1<<k);mac0++){
		gid=0;
		for(int mac=0;mac<(1<<l);mac++)
			memset(g[gid][mac],0,(m+1)<<2);
		g[gid][0][0]=1;
		
		int mac0_=mac0;
		for(int t=0;t<=m;t++,mac0_>>=1){
			int lim=min(c,t);
			gid^=1;
			for(int mac=0;mac<(1<<l);mac++)
				for(int p=0;p<=lim;p++)
					g[gid][mac][p]=g[gid^1][mac][p];
			
			for(int i=0;i<l;i++){
				int v=B[i];
				for(int mac=(1<<l)-1;mac>=0;mac--){
					if(mac>>i & 1) continue;
					for(int p=0;p<=lim;p++){
						gmod(g[gid][mac | (1<<i)][p]+=1ll*g[gid][mac][p]*dp[v][t]%mod);
					}
				}
			}
			for(int mac=0;mac<(1<<l);mac++){
				for(int p=lim;p>=0;p--){
					gmod(g[gid][mac][p+1]+=g[gid][mac][p]);
				}
			}
			
			if(!(mac0_ & 1)){
				for(int mac=0;mac<(1<<l);mac++){
					int val=1;
					for(int i=0;i<l;i++)
						if(!(mac>>i & 1)) val=1ll*val*sdp[B[i]][t+1]%mod;
					
					for(int p=0;p<=lim;p++){
						if(!g[gid^1][mac][p]) continue;
						int w=1ll*cal(c,p,n-t)*f[fid][mac0]%mod;
						
						gmod(dp[u][t]+=1ll*g[gid^1][mac][p]*val%mod*w%mod);
						
						gmod(g[gid][mac][p]+=mod-g[gid^1][mac][p]);
					}
				}
			}
		}
	}
	
	for(int i=n;i>=0;i--) gmod(sdp[u][i]=sdp[u][i+1]+dp[u][i]);
}

int main(){
//	freopen("1.txt","r",stdin);
//	freopen("2.txt","w",stdout);
	init(N-5);
	memset(pre,-1,sizeof(pre));
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v; scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	dfs(1,0);
	for(int i=0;i<=n;i++) cout<<dp[1][i]<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 37320kb

input:

5
1 2
1 3
2 4
2 5

output:

55
129
34
0
0
0

result:

wrong answer 2nd numbers differ - expected: '127', found: '129'