题目概述

AGC005F

解题报告

考虑每个点对 $k$ 的贡献：

$$ \sum_{i=1}^{n}[{n\choose k}-\sum_{(i,j)\in E}{size_j\choose k}]=n{n\choose k}-\sum_{(i,j)\in E}[{size_i\choose k}+{size_j\choose k}] $$

DFS整棵树，考虑每条边 $(fa_x,x)$ ，则两个 $size$ 分别为 $size_x$ 和 $n-size_x$ 。记 $cnt_i$ 表示 $size=i$ 的个数，则：

$$ \sum_{(i,j)\in E}[{size_i\choose k}+{size_j\choose k}]=\sum_{i=k}^{n}cnt_i{i\choose k}={1\over k!}\sum_{i=k}^{n}cnt_i\cdot i!{1\over (i-k)!} $$

显然是卷积形式。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=1<<19,MOD=924844033;

int n,si[maxn+5],INV[maxn+5],fac[maxn+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],to[(maxn<<1)+5];
int wn[maxt+5],F[maxt+5],G[maxt+5];

inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
    si[x]=1;
    for (int j=lnk[x];j;j=nxt[j])
        if (to[j]!=pre) DFS(to[j],x),si[x]+=si[to[j]];
    if (pre) F[si[x]]++,F[n-si[x]]++;
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
__attribute__((constructor)) void NTTPre(){
    int x=Pow(5,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
#define C(x,y) ((x)<(y)?0:MUL(fac[x],MUL(INV[y],INV[(x)-(y)])))
int main(){
    scanf("%d",&n);Make(n);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    DFS(1);
    for (int i=0;i<=n;i++) F[i]=MUL(F[i],fac[i]);
    for (int i=0;i<=n;i++) G[i]=INV[n-i];
    int t;for (t=1;t<=(n<<1);t<<=1);
    NTT(F,t,1);NTT(G,t,1);
    for (int i=0;i<t;i++) F[i]=MUL(F[i],G[i]);
    NTT(F,t,-1);
    for (int i=1;i<=n;i++) printf("%d\n",ADD(MUL(n,C(n,i)),MOD-MUL(INV[i],F[i+n])));
    return 0;
}