Submission #1161410

---

Source Code Expand

#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define pp pop_back
#define mp make_pair
#define pb push_back
#define rep(x, a, b) for(int x=a; x<=b; x++)
#define drp(x, a, b) for(int x=a; x>=b; x--)
typedef long long ll;
const int mod=924844033;
const int N=200200;
const int G=3;
int ans[N], n, m, l, rev[N<<2], fac[N], inv[N], f[N<<2], u[N], v[N], g[N<<2], head[N], cnt, siz[N], c[N];
ll read(){
	ll x=0; char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
	return x;
}
void write(ll x){
	if(x<10)
	{
		putchar(x+'0');
		return;
	}
	write(x/10);
	putchar(x%10+'0');
}
struct Edge{
	int to, next;
}edge[N<<1];
void AddEdge(int u, int v){
	edge[++cnt]=(Edge){ v, head[u] }, head[u]=cnt;
	edge[++cnt]=(Edge){ u, head[v] }, head[v]=cnt;
}
void dfs(int u, int fa){
	siz[u]=1;
	for(int i=head[u]; i; i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v, u);
		c[n-siz[v]]--;
		siz[u]+=siz[v];
	}
	c[siz[u]]--;
}
int power(int a, int k){
	int ret=1;
	while(k)
	{
		if(k&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod; k>>=1;
	}
	return ret;
}
void DFT(int *a, int n, int f){
	rep(i, 0, n-1) if(i<rev[i]) swap(a[i], a[rev[i]]);
	for(int i=1, t=1; i<n; i<<=1, t++)
	{
		int wn=power(G, f?(mod-1-((mod-1)>>t)):((mod-1)>>t));
		for(int j=0; j<n; j+=i<<1)
		{
			int w=1;
			for(int k=0; k<i; k++, w=1ll*w*wn%mod)
			{
				int u=a[j+k], v=1ll*w*a[j+k+i]%mod;
				a[j+k]=(u+v)%mod; a[j+k+i]=(u+mod-v)%mod;
			}
		}
	}
	if(f)
	{
		int v=power(n, mod-2);
		rep(i, 0, n-1) a[i]=1ll*a[i]*v%mod;
	}
}
int main(){
	n=read();
	fac[0]=1;
	rep(i, 1, n) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=power(fac[n], mod-2);
	drp(i, n, 1) inv[i-1]=1ll*inv[i]*i%mod;
	rep(i, 1, n-1){ u[i]=read(), v[i]=read(); AddEdge(u[i], v[i]); }
	rep(i, 1, n-1) c[i]=mod;
	dfs(1, 0);
	c[n]=n;
	rep(i, 1, n) f[i]=1ll*c[i]*fac[i]%mod;
	rep(i, 0, n) g[n-i+1]=inv[i];
	for(m=1; m<=((n<<1)|1); m<<=1) l++;
	rep(i, 0, m-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	DFT(f, m, 0); DFT(g, m, 0);
	rep(i, 0, m-1) f[i]=1ll*f[i]*g[i]%mod;
	DFT(f, m, 1);
	rep(k, 1, n) ans[k]=1ll*inv[k]*f[n+k+1]%mod;
	rep(i, 1, n) write(ans[i]), puts("");
}

Submission Info

Judge Result