Submission #1680444

---

Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int MAXN = 524300;
const int mo = 924844033;
const int g = 5;

int N,L;
LL a[MAXN],b[MAXN],mi[MAXN];
int n;
LL cnt[MAXN];
LL inv[MAXN],js[MAXN];
struct edge{
	int x,nxt;
}e[MAXN];
int h[MAXN],tot;
int bitr[MAXN];
int siz[MAXN];
LL ny;

LL quickmi(LL x,LL tim){LL ans=1;x%=mo;for(;tim;tim/=2,x=x*x%mo)if (tim&1)ans=ans*x%mo;return ans;}

void inse(int x,int y){e[++tot].x=y;e[tot].nxt=h[x];h[x]=tot;}

void prepare(){
	inv[0]=inv[1]=1;
	fo(i,2,n)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
	fo(i,1,n)inv[i]=1ll*inv[i]*inv[i-1]%mo;
	js[0]=js[1]=1;
	fo(i,1,n)js[i]=js[i-1]*i%mo;
	N=1,L=0;
	while(N<=n*2)N<<=1,L++;
	fo(i,0,N-1){
		bitr[i]=0;
		fo(j,0,L-1)
		if (((1<<j)&i)>0)bitr[i]+=(1<<(L-1-j));
	}
	LL G=quickmi(g,(mo-1)/N);
	mi[0]=1;
	fo(i,1,N)mi[i]=mi[i-1]*G%mo;
	ny=quickmi(N,mo-2);
}

void dfs(int x){
	siz[x]=1;
	for(int p=h[x];p;p=e[p].nxt)
	if (!siz[e[p].x]){
		dfs(e[p].x);
		siz[x]+=siz[e[p].x];
	}
	if (x>1){
		cnt[siz[x]]++;
		cnt[n-siz[x]]++;
	}
}

LL calc(int n,int m){return 1ll*js[n]*inv[m]%mo*inv[n-m]%mo;}

LL add(LL x,LL y){return x+y>=mo?x+y-mo:x+y;}

LL dec(LL x,LL y){return x>=y?x-y:x+mo-y;}

void DFT(LL *a){
	fo(i,0,N-1)
	if (i<bitr[i])swap(a[i],a[bitr[i]]);
	for(int now=2;now<=N;now<<=1){
		int half=now/2;
		fo(i,0,half-1){
			LL w=mi[N/now*i];
			for(int j=i;j<N;j+=now){
				LL l=a[j],r=w*a[j+half]%mo;
				a[j]=add(l,r);
				a[j+half]=dec(l,r);
			}
		}
	}
}

void IDFT(LL *a){
	fo(i,0,N-1)
	if (i<bitr[i])swap(a[i],a[bitr[i]]);
	for(int now=2;now<=N;now<<=1){
		int half=now/2;
		fo(i,0,half-1){
			LL w=mi[N-N/now*i];
			for(int j=i;j<N;j+=now){
				LL l=a[j],r=w*a[j+half]%mo;
				a[j]=add(l,r);
				a[j+half]=dec(l,r);
			}
		}
	}
	fo(i,0,N-1)a[i]=ny*a[i]%mo;
}

void ntt(LL *a,LL *b){
	DFT(a);DFT(b);
	fo(i,0,N-1)a[i]=1ll*a[i]*b[i]%mo;
	IDFT(a);
}

int main(){
	n=get();
	fo(i,2,n){
		int x=get(),y=get();
		inse(x,y),inse(y,x);
	}
	prepare();
	dfs(1);
	fo(i,0,n)a[n-i]=1ll*cnt[i]*js[i]%mo;
	fo(i,0,n)b[i]=inv[i];
	ntt(a,b);
	fo(i,0,n/2)swap(a[i],a[n-i]);
	fo(i,1,n){
		LL v=1ll*a[i]*inv[i]%mo;
		v=(1ll*calc(n,i)*n%mo+mo-v)%mo;
		printf("%lld\n",v);
	}
	return 0;
}

Submission Info

Judge Result