Submission #1161333

---

Source Code Expand

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<sstream>
#include<numeric>
#include<iostream>
#include<algorithm>
#include<functional>
 
#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
 
typedef long long ll;
typedef double db;
typedef vector<int> Vi;
typedef pair<int,int> pii;
 
int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}
 
const int N=200000*4+19;
const int p=924844033;
 
int Pow(int a,int b){
	int res=1;
	for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
	return res;
}
 
int W[2][N],rev[N],c;
void Prepare(int n){
	int pw=1,pi=1,w0=Pow(5,(p-1)/n),i0=Pow(w0,p-2);
	For(i,0,n){
		W[0][i]=pw,pw=1ll*pw*w0%p;
		W[1][i]=pi,pi=1ll*pi*i0%p;
		rev[i]=0;
		for (int x=i,&y=rev[i],k=1;k<n;k<<=1,x>>=1) y=(y<<1)|(x&1);
	}
}
void FFT(int *A,int n,int f){
	For(i,0,n) if (i<rev[i]) swap(A[i],A[rev[i]]);
	for (int i=1;i<n;i<<=1)
		for (int j=0,t=n/(i<<1);j<n;j+=i<<1)
			for (int k=j,l=0;k<j+i;k++,l+=t){
				int x=A[k],y=1ll*W[f][l]*A[k+i]%p;
				A[k]=(x+y)%p;A[k+i]=(x-y+p)%p;
			}
	if (f){
		int tmp=Pow(n,p-2);
		For(i,0,n) A[i]=1ll*A[i]*tmp%p;
	}
}
 
struct Edge{
	int y,nxt;
} E[N*2];
int fac[N],inv[N],las[N],sz[N],A[N],F[N],B[N];
int n,cnt;
 
int C(int n,int m){
	if (n<m) return 0;
	return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;
}
void Link(int x,int y){
	E[cnt]=(Edge){y,las[x]};las[x]=cnt++;
	E[cnt]=(Edge){x,las[y]};las[y]=cnt++;
}
void dfs(int x,int fa){
	sz[x]=1;
	for (int i=las[x],y;~i;i=E[i].nxt)
		if ((y=E[i].y)!=fa){
			dfs(y,x);
			sz[x]+=sz[y];
			A[sz[y]]++;
		}
	A[n-sz[x]]++;
}
 
int main(){
	memset(las,-1,sizeof(las));
	fac[0]=1;
	For(i,1,N) fac[i]=1ll*fac[i-1]*i%p;
	inv[N-1]=Pow(fac[N-1],p-2);
	for (int i=N-1;i;i--) inv[i-1]=1ll*inv[i]*i%p;
	n=IN();
	For(i,1,n) Link(IN(),IN());
	dfs(1,-1);
	For(i,1,n+1) A[i]=1ll*A[i]*fac[i]%p;
	For(i,0,n) B[n-i]=inv[i];
	
	for (c=1;c<=n;c<<=1);c<<=1;
	Prepare(c);
	FFT(A,c,0);FFT(B,c,0);
	For(i,0,c) A[i]=1ll*A[i]*B[i]%p;
	FFT(A,c,1);
	
	For(k,1,n+1){
		F[k]=(1ll*inv[k]%p*A[k+n])%p;
		F[k]=(F[k]+1ll*C(n,k)*k+1ll*C(n-1,k)*n)%p;
	}
	For(i,1,n+1) printf("%d\n",F[i]);
}

Submission Info

Judge Result