「AGC 005F」Many Easy Problems

发表于

给定一棵 nn 个节点的树，选出 kk 个特殊点，假设点集为 SS，令 f(S)f(S) 为最小的包含这 kk 个节点的连通块，分别求出 k=1⋯nk=1\cdots n 在所有情况下的 f(S)f(S) 的和。

Constraints

2≤n≤2000002 \leq n \leq 200000

Solution

考虑暴力，一个点被统计在连通块内，即在以它为根时，选出来的 kk 个点都在它的同一个儿子的子树内。即节点 xx 被统计进答案的次数 g(x)g(x) 为：

g(x)=(nk)−∑(x,i)⊆E(szik)g(x)=\binom{n}{k}-\sum _{(x,i)\subseteq E}\binom{sz_{i}}{k}

令 cntxcnt_{x} 表示上述公式里有多少个 szi=xsz_{i}=x，那么可以得到：

ansk=∑i=1ncnti⋅(ik)ans_{k}=\sum _{i=1}^{n}cnt_{i}\cdot\binom{i}{k}

整理可得：

k!⋅ansk=∑i=1ncnti⋅i!(i−k)!k!\cdot ans_{k}=\sum _{i=1}^{n}\frac{cnt_{i}\cdot i!}{(i-k)!}

令 ai=cnti⋅i!a_{i}=cnt_{i}\cdot i!，bi=(n−i)!b_{i}=(n-i)!，则可得：

k!⋅ansk=∑i=1nai⋅bn−i+kk!\cdot ans_{k}=\sum _{i=1}^{n}a_{i}\cdot b_{n-i+k}

最终答案为 n⋅(nk)−anskn\cdot \binom{n}{k}-ans_{k} 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
const int M=524288+5;
const int mod=924844033; 
int n,nn,cnt,u,v,ans,first[N],fac[N],inv[N];
int num[N],sz[N],a[M],b[M];
struct edge{int to,next;}e[N*2];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void dfs(int x,int fa)
{
    sz[x]=1;
    for(int i=first[x];i;i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa)continue;
        dfs(to,x);
        sz[x]+=sz[to];
    }
    if(fa!=-1)a[sz[x]]++,a[n-sz[x]]++;
}
int power(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;b>>=1;
    }
    return ans;
}
void ntt(int *a,int n,int f)
{
    int k=0;while((1<<k)<n)k++;
    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=0;j<k;j++)
            if(i&(1<<j))t|=(1<<(k-j-1));
        if(i<t)swap(a[i],a[t]);
    }
    for(int l=2;l<=n;l<<=1)
    {
        int m=l>>1,nw=power(5,(mod-1)/l);
        if(f==-1)nw=power(nw,mod-2);
        for(int *p=a;p!=a+n;p+=l)
        {
            int w=1;
            for(int i=0;i<m;i++)
            {
                int t=1ll*p[m+i]*w%mod;
                p[m+i]=(p[i]-t+mod)%mod;
                p[i]=(p[i]+t)%mod;
                w=1ll*w*nw%mod;
            }
        }
    }
    if(f==-1)
    {
        int inv=power(n,mod-2);
        for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
    }
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        u=read();v=read();
        ins(u,v);ins(v,u);
    }
    dfs(1,-1);
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=power(fac[n],mod-2);
    for(int i=n;i>=1;i--)inv[i-1]=1ll*inv[i]*i%mod;
    for(int i=1;i<=n;i++)a[i]=1ll*a[i]*fac[i]%mod;
    for(int i=0;i<=n;i++)b[n-i]=inv[i];
    nn=1;while(nn<n+n+1)nn<<=1;
    ntt(a,nn,1);ntt(b,nn,1);
    for(int i=0;i<nn;i++)a[i]=1ll*a[i]*b[i]%mod;
    ntt(a,nn,-1);
    for(int i=1;i<=n;i++)
    {
        ans=1ll*fac[n]*inv[i]%mod*inv[n-i]%mod*n%mod;
        printf("%lld\n",(ans-1ll*a[n+i]*inv[i]%mod+mod)%mod);
    }
    return 0;
}