提出 #18407878

---

ソースコード 拡げる

/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define mod 924844033
#define int long long
using namespace std;
const int N=2*1e5+100;
int n,sz[N],f[N*4],g[N*4],rev[N*4],len,fac[N],inv[N];
int tot,first[N],nxt[N*2],point[N*2];
inline void add(int &a,int b){a=((a+b>mod)?a+b-mod:a+b);}
inline void del(int &a,int b){a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){a=(a*b)%mod;}
inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void add_edge(int x,int y)
{
	nxt[++tot]=first[x];
	first[x]=tot;
	point[tot]=y;
}
inline void change(int len)
{
	for (int i=0;i<len;i++)
	{
		rev[i]=rev[i>>1]>>1;
		if (i&1) rev[i]|=len>>1;
	}
}
inline void ntt(int y[],int len,int v)
{
	for (int i=0;i<len;i++) if (i<rev[i]) swap(y[i],y[rev[i]]);
	for (int i=2;i<=len;i<<=1)
	{
		int step=m_pow(5,(mod-1)/i);
		if (v==-1) step=m_pow(step,mod-2);
		for (int j=0;j<len;j+=i)
		{
			int x=1;
			for (int k=j;k<j+i/2;k++)
			{
				int a=y[k],b=x*y[k+i/2]%mod;
				y[k]=(a+b)%mod;
				y[k+i/2]=(a-b+mod)%mod;
				mul(x,step);
			}
		}
	}
	if (v==-1)
	{
		int invlen=m_pow(len,mod-2);
		for (int i=0;i<len;i++) mul(y[i],invlen);
	}
}
void dfs(int x,int fa)
{
	sz[x]=1;
	for (int i=first[x];i!=-1;i=nxt[i])
	{
		int u=point[i];if (u==fa) continue;
		dfs(u,x);
		sz[x]+=sz[u];
	}
}
inline void print(int y[],int len)
{
	for (int i=0;i<len;i++) printf("%lld ",y[i]);
	printf("\n");
}
signed main()
{
	tot=-1;
	memset(first,-1,sizeof(first));
	n=read();
	for (int i=1;i<n;i++)
	{
		int u=read(),v=read();
		add_edge(u,v);add_edge(v,u);
	}
	dfs(1,1);
	for (int i=2;i<=n;i++) f[sz[i]]++,f[n-sz[i]]++;
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n]=m_pow(fac[n],mod-2);
	for (int i=n-1;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%mod;
	for (int i=0;i<=n;i++) g[i]=inv[i],mul(f[i],fac[i]);
	reverse(g,g+1+n);
	len=1;while (len<=n+n) len<<=1;change(len);
	ntt(f,len,1);ntt(g,len,1);
	for (int i=0;i<len;i++) mul(f[i],g[i]);
	ntt(f,len,-1);
	for (int i=1;i<=n;i++)
	{
		int ans=n*C(n,i)%mod;
		del(ans,f[n+i]*inv[i]%mod);
		printf("%lld\n",ans);
	}
}

提出情報

ジャッジ結果