【AGC005F】Many Easy Problems

Description

　　

　　题目链接

　　

　　对于每个\(k\)，统计任选\(k\)个点作为关键点的“最小生成树”的大小之和

　　

Solution

　　

　　正向想法是枚举或者计算大小为\(x\)、叶子数目为\(y\)的子树有多少种，然后贡献答案。这种方法参数多、难统计，可以感受到无法适应\(1e5\)的数据，舍弃

　　

　　正难则反，自顶向下正向统计难，就考虑自底向上贡献统计。那么这里的自底向上，就应该是对于每一个点，统计其贡献到每个\(ans\)的次数，并累加。

　　

　　既然要输出k=1...m的答案，可以猜到贡献是一个卷积加速的形式

　　

　　所以先考虑每个点对某一个k的答案的贡献

　　

　　任选k个点之后，一个点对答案有1的贡献，当且仅当选择的点不全在以其为根时的某棵子树中

　　

　　这个很好统计，不全在某棵子树中这个条件很难考虑，不如直接用总数减去不合法的方案，毕竟所有元素用一个组合数就可以搞定\({n \choose k}-\sum_v {size_v\choose k}\)

　　

　　则

\[ans_k=\sum_{u=1}^n{n \choose k}-\sum_{v\in \text{sub}_u}{size_v \choose k}
\]

　　前一部分可以直接算，但后一部分看起来不是一个数组的卷积

　　

　　遇到这种情况，我们可以用权值作为下标先做一个统计数组\(a[size_v]++\)，因为统计时使用的数据与这个\(size_v\)具体是哪一个点的子树大小关系不大，而只和子树大小这个数值有关。因此不以每个点作为视角考虑（具体是谁不重要），而以整棵树为视角考虑，那么\(ans_k\)就会变成

\[ans_k=n{n\choose k}-\sum_{i=1}^{n-1}a_i{i \choose k}
\]

　　

　　减法卷积算出每个\(ans_k\)的负部分即可

Code

#include <cstdio>

using namespace std;

namespace IO{

    const int S=10000000;

    char buf[S];

    int pos;

    void load(){

        fread(buf,1,S,stdin);

        pos=0;

    }

    char getChar(){

        return buf[pos++];

    }

    int getInt(){

        int x=0,f=1;

        char c=getChar();

        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getChar();}

        while('0'<=c&&c<='9'){x=x*10+c-'0';c=getChar();}

        return x*f;

    }

}

using IO::getInt;

const int N=200005;

const int MOD=924844033,G=5;

int n;

int h[N],tot;

struct Edge{

    int v,next;

}e[N*2];

int size[N],sum[N];

int fact[N],iact[N];

inline void swap(int &x,int &y){

    x^=y^=x^=y;

}

void addEdge(int u,int v){

    e[++tot]=(Edge){v,h[u]}; h[u]=tot;

    e[++tot]=(Edge){u,h[v]}; h[v]=tot;

}

void readData(){

    n=getInt();

    int u,v;

    for(int i=1;i<n;i++){

        u=getInt(); v=getInt();

        addEdge(u,v);

    }

}

void dfs(int u,int fa){

    size[u]=1;

    for(int i=h[u],v;i;i=e[i].next)

        if((v=e[i].v)!=fa){

            dfs(v,u);

            size[u]+=size[v];

            sum[size[v]]++;

        }

    sum[n-size[u]]++;

}

int fmi(int x,int y){

    int res=1;

    for(;y;x=1ll*x*x%MOD,y>>=1)

        if(y&1)

            res=1ll*res*x%MOD;

    return res;

}

void init(){

    fact[0]=1;

    for(int i=1;i<=n;i++)

        fact[i]=1ll*fact[i-1]*i%MOD;

    iact[0]=iact[1]=1;

    if(n>1){

        iact[n]=fmi(fact[n],MOD-2);

        for(int i=n-1;i>=2;i--)

            iact[i]=1ll*iact[i+1]*(i+1)%MOD;

    }

}

inline int C(int n,int m){

    return m>n?0:1ll*fact[n]*iact[m]%MOD*iact[n-m]%MOD;

}

namespace NTT{/*{{{*/

    const int S=N*4,B=19;

    int n,invn,bit;

    int rev[S],W[S][2];

    void build(){

        int iG=fmi(G,MOD-2);

        for(int i=0;i<=B;i++){

            W[1<<i][0]=fmi(G,(MOD-1)/(1<<i));

            W[1<<i][1]=fmi(iG,(MOD-1)/(1<<i));

        }

    }

    void init(int _n){

        for(n=1,bit=0;n<_n;n<<=1,bit++);

        invn=fmi(n,MOD-2);

        for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));

    }

    void ntt(int *a,int f){

        for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);

        int w_n,w,u,v;

        for(int i=2;i<=n;i<<=1){

            w_n=W[i][f];

            for(int j=0;j<n;j+=i){

                w=1;

                for(int k=0;k<(i>>1);k++){

                    u=a[j+k];

                    v=1ll*w*a[j+(i>>1)+k]%MOD;

                    a[j+k]=(u+v)%MOD;

                    a[j+(i>>1)+k]=(u-v)%MOD;

                    w=1ll*w*w_n%MOD;

                }

            }

        }

        if(f)

            for(int i=0;i<n;i++) a[i]=1ll*a[i]*invn%MOD;

    }

}/*}}}*/

void solve(){

    static int a[NTT::S],b[NTT::S];

    for(int i=0;i<n;i++){

        a[i]=1ll*sum[i]*fact[i]%MOD;

        b[i]=iact[n-1-i];

    }

    NTT::init(n+n-1);

    NTT::ntt(a,0);

    NTT::ntt(b,0);

    for(int i=0;i<NTT::n;i++) a[i]=1ll*a[i]*b[i]%MOD;

    NTT::ntt(a,1);

    // now a[n],a[n+1],... represent k=1,2,3,...

    int ans;

    for(int k=1;k<=n;k++){

        ans=(1ll*n*C(n,k)%MOD-1ll*iact[k]*a[n-1+k]%MOD)%MOD;

        printf("%d\n",ans<0?ans+MOD:ans);

    }

}

int main(){

    IO::load();

    NTT::build();

    readData();

    dfs(1,0);

    init();

    solve();

    return 0;

}

巴特西

【AGC005F】Many Easy Problems

Description

Solution

Code

最新文章

热门文章