哈哈

原题链接：803.Circus--Platinum

万物之初

2024-08-20 16:35:13

发布于：江西

18阅读

0回复

0点赞

能在这里发题解的人肯定都是聪明人，我一个只能做入门题目的人就不凑热闹了

有帮助，赞一个

去预览

0/2000

全部评论 1

༺ཌༀTN黑客ༀད༻

USACO的题还算简单，只需要

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int ksm(int x,int y){
	int z=1;
	for(;y;x=1ll*x*x%mod,y>>=1)if(y&1)z=1ll*z*x%mod;
	return z;
}
int n,fac[100100],inv[100100],res[100100];
vector<int>g[100100],key;
struct dsu{
	int fa,ins,out;
}a[100100];
void init(){
	for(int i=1;i<=n;i++)if(g[i].size()!=2)a[i].fa=i,a[i].out=g[i].size(),key.push_back(i);
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int find(int x){
	return a[x].fa==x?x:a[x].fa=find(a[x].fa);
}
void merge(int x,int y,int z){
	x=find(x),y=find(y);
	if(x==y)return;
	key.erase(lower_bound(key.begin(),key.end(),y));
	a[x].ins+=a[y].ins+z-1,a[x].out+=a[y].out-2,a[y].fa=x;
}
struct path{
	int x,y,z;
	path(int u,int v,int w){x=u,y=v,z=w;}
	friend bool operator <(const path &x,const path &y){
		return x.z<y.z;
	}
};
vector<path>paths;
void getpath(int x,int fa,int len,int from){
	if(g[x].size()!=2){
		if(from)paths.push_back(path(from,x,len));
		len=1,from=x;
	}
	for(auto y:g[x])if(y!=fa)getpath(y,x,len+1,from);
}
int main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
	init();
	getpath(key.front(),0,0,0);
	sort(paths.begin(),paths.end());
	for(int i=n-1,j=0;i;i--){
		while(j<paths.size()&&i<n-paths[j].z)merge(paths[j].x,paths[j].y,paths[j].z),j++;
		res[i]=fac[i];
		for(auto x:key)res[i]=1ll*res[i]*inv[i-(n-a[x].ins-1)+a[x].out*(n-i-1)]%mod;
	}
	res[n]=fac[n];
	for(int i=1;i<=n;i++)printf("%d\n",res[i]);
	return 0;
}

1周前来自北京

‮队团加不）ด้้童帅_者仇复
回复༺ཌༀTN黑客ༀད༻
啥如掉

1周前来自广东
0

༺ཌༀTN黑客ༀད༻

回复‮队团加不）ด้้童帅_者仇复

记住，只需要

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int ksm(int x,int y){
	int z=1;
	for(;y;x=1ll*x*x%mod,y>>=1)if(y&1)z=1ll*z*x%mod;
	return z;
}
int n,fac[100100],inv[100100],res[100100];
vector<int>g[100100],key;
struct dsu{
	int fa,ins,out;
}a[100100];
void init(){
	for(int i=1;i<=n;i++)if(g[i].size()!=2)a[i].fa=i,a[i].out=g[i].size(),key.push_back(i);
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int find(int x){
	return a[x].fa==x?x:a[x].fa=find(a[x].fa);
}
void merge(int x,int y,int z){
	x=find(x),y=find(y);
	if(x==y)return;
	key.erase(lower_bound(key.begin(),key.end(),y));
	a[x].ins+=a[y].ins+z-1,a[x].out+=a[y].out-2,a[y].fa=x;
}
struct path{
	int x,y,z;
	path(int u,int v,int w){x=u,y=v,z=w;}
	friend bool operator <(const path &x,const path &y){
		return x.z<y.z;
	}
};
vector<path>paths;
void getpath(int x,int fa,int len,int from){
	if(g[x].size()!=2){
		if(from)paths.push_back(path(from,x,len));
		len=1,from=x;
	}
	for(auto y:g[x])if(y!=fa)getpath(y,x,len+1,from);
}
int main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
	init();
	getpath(key.front(),0,0,0);
	sort(paths.begin(),paths.end());
	for(int i=n-1,j=0;i;i--){
		while(j<paths.size()&&i<n-paths[j].z)merge(paths[j].x,paths[j].y,paths[j].z),j++;
		res[i]=fac[i];
		for(auto x:key)res[i]=1ll*res[i]*inv[i-(n-a[x].ins-1)+a[x].out*(n-i-1)]%mod;
	}
	res[n]=fac[n];
	for(int i=1;i<=n;i++)printf("%d\n",res[i]);
	return 0;
}

1周前来自北京

‮队团加不）ด้้童帅_者仇复
回复༺ཌༀTN黑客ༀད༻
人机抄袭谁不会啊

1周前来自广东
0

全部评论 1

热门讨论