题解：AT_agc005_f [AGC005F] Many Easy Problems
ax_by_c
·
·
题解
考虑拆贡献，对于点 $u$ 会被覆盖 $\binom{n}{k}-\sum_{(u,v)\in E}\binom{sz_{v,u}}{k}$ 次，其中 $sz_{v,u}$ 表示以 $u$ 为根时 $v$ 子树的大小。
因此有 $f(k)=n\binom{n}{k}-\sum_{(u,v)\in E}\binom{sz_{v,u}}{k}$，前面的容易计算，只需关心 $\sum_{(u,v)\in E}\binom{sz_{v,u}}{k}$，设其为 $g(k)$。
容易求出 $cnt_x=\sum_{(u,v)\in E}[sz_{v,u}=x]$，则 $g(k)=\sum_xcnt_x\binom{x}{k}=\sum_x\frac{cnt_xx!}{k!(x-k)!}$。
因此 $k!g(k)=\sum_x\frac{cnt_xx!}{(x-k)!}$。
令 $A_i=cnt_ii!,B_i=\frac{1}{i!}$，则 $k!g(k)=\sum_{x-y=k}A_xB_y$。
显然考虑将 $B$ 下标取相反数，同时为了方便设 $C_i=B_{n-i}$，则 $k!g(k)=[x^{n+k}]AC$，ntt 即可。
时间复杂度 $O(n\log n)$，$924844033$ 的原根是 $5$。
```cpp
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define repll(i,l,r) for(ll i=(l);i<=(r);i++)
#define perll(i,r,l) for(ll i=(r);i>=(l);i--)
#define pb push_back
#define ins insert
#define clr clear
using namespace std;
namespace ax_by_c{
typedef long long ll;
const ll mod=924844033;
const int N=1e6+5;
ll ksm(ll a,ll b,ll p){
a=a%p;
ll r=1;
while(b){
if(b&1)r=r*a%p;
a=a*a%p;
b>>=1;
}
return r%p;
}
ll fac[N],inv[N];
void Init(int n){
fac[0]=1;
rep(i,1,n)fac[i]=fac[i-1]*i%mod;
inv[n]=ksm(fac[n],mod-2,mod);
per(i,n,1)inv[i-1]=inv[i]*i%mod;
}
ll C(int n,int m){
if(n<0||m<0||n<m)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
namespace Bpoly{
const ll G=5;
const ll IG=554906420;
int to[N];
void ntt(ll *a,int p,int z){
rep(i,0,p-1)if(i<to[i])swap(a[i],a[to[i]]);
for(int k=2;k<=p;k<<=1){
ll g=ksm((z==1)?G:IG,(mod-1)/k,mod);
for(int i=0;i<p;i+=k){
ll x=1;
for(int j=0;j<k>>1;j++){
ll A=a[i+j],B=a[i+j+(k>>1)];
a[i+j]=(A+x*B%mod)%mod;
a[i+j+(k>>1)]=(A-x*B%mod+mod)%mod;
x=x*g%mod;
}
}
}
}
void convolution(ll *a,ll *b,ll *c,int n,int m){
int p=1;
while(p<=(n+m))p<<=1;
rep(i,0,p-1)to[i]=(to[i>>1]>>1)|((i&1)*(p>>1));
ntt(a,p,1);
ntt(b,p,1);
rep(i,0,p-1)c[i]=a[i]*b[i]%mod;
ntt(c,p,-1);
rep(i,0,p-1)c[i]=c[i]*ksm(p,mod-2,mod)%mod;
}
};
ll a[N],b[N],c[N];
int n,sz[N],cnt[N];
vector<int>g[N];
void dfs(int u,int fa){
sz[u]=1;
for(auto v:g[u]){
if(v==fa)continue;
dfs(v,u);
sz[u]+=sz[v];
cnt[sz[v]]++,cnt[n-sz[v]]++;
}
}
void slv(int _csid,int _csi){
scanf("%d",&n);
rep(i,1,n-1){
int x,y;
scanf("%d %d",&x,&y);
g[x].pb(y);
g[y].pb(x);
}
dfs(1,0);
Init(n);
rep(i,0,n)a[i]=fac[i]*cnt[i]%mod,b[n-i]=inv[i];
Bpoly::convolution(a,b,c,n,n);
rep(i,1,n)printf("%lld\n",(C(n,i)*n%mod-c[n+i]*inv[i]%mod+mod)%mod);
}
void main(){
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1,csid=0;
// scanf("%d",&csid);
// scanf("%d",&T);
rep(i,1,T)slv(csid,i);
}
}
int main(){
string __name="";
if(__name!=""){
freopen((__name+".in").c_str(),"r",stdin);
freopen((__name+".out").c_str(),"w",stdout);
}
ax_by_c::main();
return 0;
}
```