题目链接
AtCoder：https://agc005.contest.atcoder.jp/tasks/agc005_f
洛谷：https://www.luogu.org/problemnew/show/AT2064
Solution
注意到模数为\(441\cdot 2^{21}+1\)，嘿嘿
首先要想到考虑贡献，然后这题就简单了。
设当前要算的为\(f(i)\)，我们考虑第\(x\)个点的贡献，显然可以得到贡献为：
\[\binom{n}{i}-\sum_{v\in son_{x}}\binom{sz_v}{i}
\]
\]
就是所有的方案减去这个点选不到的方案，其中\(sz_v\)表示以\(x\)为根\(v\)的\(\rm size\)。
然后累和：
\[\begin{align}
f(i)&=\sum_{x=1}^{n}\left(\binom{n}{i}-\sum_{v\in son_{x}}\binom{sz_v}{i}\right)\\
&=n\binom{n}{i}-\sum_{x=1}^{n}\sum_{v\in son_x}\binom{sz_v}{i}
\end{align}
\]
f(i)&=\sum_{x=1}^{n}\left(\binom{n}{i}-\sum_{v\in son_{x}}\binom{sz_v}{i}\right)\\
&=n\binom{n}{i}-\sum_{x=1}^{n}\sum_{v\in son_x}\binom{sz_v}{i}
\end{align}
\]
后面那块不好处理，我们可以记个桶\(cnt(s)\)表示大小为\(s\)的子树出现了多少次，这个一遍\(\rm dfs\)就可以算出来。
那么把式子化一下：
\[\begin{align}
f(i)&=n\binom{n}{i}-\sum_{j=1}^{n}cnt(j)\binom{j}{i}\\
&=n\binom{n}{i}-\frac{1}{i!}\sum_{j=i}^{n}\frac{cnt(j)j!}{(j-i)!}
\end{align}
\]
f(i)&=n\binom{n}{i}-\sum_{j=1}^{n}cnt(j)\binom{j}{i}\\
&=n\binom{n}{i}-\frac{1}{i!}\sum_{j=i}^{n}\frac{cnt(j)j!}{(j-i)!}
\end{align}
\]
注意到后面可以转化为卷积的形式，设：
\[g(i)=cnt(i)i!,h(i)=\frac{1}{i!}
\]
\]
后面的\(\sum\)就是：
\[\sum_{j=i}^{n}g(j)h(j-i)=\sum_{j=0}^{n-i}g(j-i)h(j)
\]
\]
我们\(\rm reverse\)一下\(g\)：
\[\sum_{j=0}^{n-i}g_R((n-i)-j)h(j)
\]
\]
\(NTT\)优化就好了，复杂度\(O(n\log n)\)。
注意这个神奇的模数原根是\(5\)，我一开始写成\(3\)还以为是\(NTT\)挂了...
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define end puts("NO"),exit(0)
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 924844033;
int add(int x,int y) {return x+y>mod?x+y-mod:x+y;}
int del(int x,int y) {return x-y<0?x-y+mod:x-y;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=mul(a,a)) if(x&1) res=mul(a,res);
return res;
}
int fac[maxn],ifac[maxn],inv[maxn],pos[maxn],N,mxn,bit,n;
int w[maxn],rw[maxn],f[maxn],g[maxn],h[maxn],head[maxn],tot,sz[maxn];
struct edge{int to,nxt;}e[maxn<<1];
void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
void dfs(int x,int fa) {
sz[x]=1;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to!=fa) dfs(e[i].to,x),sz[x]+=sz[e[i].to],g[sz[e[i].to]]++;
g[n-sz[x]]++;
}
void ntt_init() {
w[0]=rw[0]=1,w[1]=qpow(5,(mod-1)/mxn);
for(int i=2;i<=mxn;i++) w[i]=mul(w[i-1],w[1]);
rw[1]=qpow(w[1],mod-2);
for(int i=2;i<=mxn;i++) rw[i]=mul(rw[i-1],rw[1]);
}
void ntt_get(int len) {
for(bit=0,N=1;N<=len;N<<=1,bit++);
for(int i=0;i<N;i++) pos[i]=pos[i>>1]>>1|((i&1)<<(bit-1));
}
void ntt(int *r,int op) {
for(int i=1;i<N;i++) if(pos[i]>i) swap(r[i],r[pos[i]]);
for(int i=1,d=mxn>>1;i<N;i<<=1,d>>=1)
for(int j=0;j<N;j+=i<<1)
for(int k=0;k<i;k++) {
int x=r[j+k],y=mul((op==-1?rw:w)[k*d],r[i+j+k]);
r[j+k]=add(x,y),r[i+j+k]=del(x,y);
}
if(op==-1) {int d=qpow(N,mod-2);for(int i=0;i<N;i++) r[i]=mul(r[i],d);}
}
int main() {
read(n);for(int x,y,i=1;i<n;i++) read(x),read(y),ins(x,y),ins(y,x);
dfs(1,0);fac[0]=ifac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
for(int i=2;i<=n;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
for(int i=1;i<=n;i++) ifac[i]=mul(ifac[i-1],inv[i]);
for(int i=0;i<=n;i++) h[i]=ifac[i],g[i]=mul(g[i],fac[i]);
g[0]=0;
reverse(g,g+n+1);for(mxn=1;mxn<=n<<1;mxn<<=1);
ntt_init(),ntt_get(n<<1),ntt(g,1),ntt(h,1);
for(int i=0;i<N;i++) f[i]=mul(g[i],h[i]);
ntt(f,-1);
for(int i=1;i<=n;i++) write(del(mul(n,mul(fac[n],mul(ifac[i],ifac[n-i]))),mul(ifac[i],f[n-i])));
return 0;
}