哈哈

全部评论 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;
  }
  

  2天前 来自 北京

  0
  • 

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

    回复༺ཌༀTN黑客ༀད༻

    啥如掉

    2天前 来自 广东

    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;
    }
    

    2天前 来自 北京

    0
  • 

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

    回复༺ཌༀTN黑客ༀད༻

    人机 抄袭谁不会啊

    2天前 来自 广东

    0