提出 #25305769

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int s=1,a=0;
	char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') s=-s;
		c=getchar();
	}
	while(isdigit(c)) {
		a=a*10+c-'0';
		c=getchar();
	}
	return s*a;
}
const int N=6e5+8,Mod=924844033,G=5,IG=554906420;
int re[N],f[N],g[N],jc[N],jcinv[N],n;
int ksm(int a,int b) {
	int c=1;
	while(b) {
		if(b&1) c*=a,c%=Mod;
		a*=a,a%=Mod;
		b>>=1;
	}
	return c;
}
void init() {
	jc[0]=1;
	for(int i=1; i<=n; i++) jc[i]=jc[i-1]*i%Mod;
	jcinv[n]=ksm(jc[n],Mod-2);
	for(int i=n; i>=1; i--) jcinv[i-1]=jcinv[i]*i%Mod;
}
void ntt(int *arr,int len,int op) {
	for(int i=0; i<len; i++) {
		if(i<re[i]) swap(arr[i],arr[re[i]]);
	}
	for(int i=2; i<=len; i<<=1) {
		int wn=ksm(op==1?G:IG,(Mod-1)/i);
		for(int j=0; j<len; j+=i) {
			int wk=1;
			for(int k=j; k<j+(i>>1); k++,wk=wk*wn%Mod) {
				int xx=arr[k],yy=arr[k+(i>>1)]*wk%Mod;
				arr[k]=(xx+yy)%Mod;
				arr[k+(i>>1)]=(xx-yy+Mod)%Mod;
			}
		}
	}
}
int C(int a,int b) {
	return jc[a]*jcinv[b]%Mod*jcinv[a-b]%Mod;
}
int siz[N],cnt[N];
vector <int> T[N];
void dfs(int u,int fa) {
	siz[u]=1;
	for(auto v:T[u]) {
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=siz[v];
		cnt[siz[v]]++;
	}
	cnt[n-siz[u]]++;
}
int ans[N];
signed main() {
	n=read();
	for(int i=1; i<n; i++) {
		int a=read(),b=read();
		T[a].push_back(b);
		T[b].push_back(a);
	}
	dfs(1,0);
	init();
	for(int i=1; i<=n; i++) {
		f[n-i]=cnt[i]*jc[i]%Mod;
		g[i]=jcinv[i];
	}
	g[0]=1;
	int len=1,tim=0;
	while(len<=(n<<1)) len<<=1,tim++;
	int invlen=ksm(len,Mod-2);
	for(int i=0; i<len; i++) re[i]=(re[i>>1]>>1)|((i&1)<<(tim-1));
	ntt(f,len,1),ntt(g,len,1);
	for(int i=0; i<len; i++) f[i]=f[i]*g[i]%Mod;
	ntt(f,len,-1);
	for(int i=0; i<len; i++) f[i]=f[i]*invlen%Mod;
//	reverse(f,f+n+1);
	for(int i=1; i<=n; i++) {
		ans[i]=(C(n,i)*n%Mod-jcinv[i]*f[n-i]%Mod+Mod)%Mod;
	}
	for(int i=1; i<=n; i++) printf("%lld\n",ans[i]);
	return 0;
}

提出情報

ジャッジ結果