[WC2019] 数树

[WC2019] 数树

Zhang_RQ题解（本篇仅概述）

前言

有进步，只做了半天。。。。

一道具有极强综合性的数数好题！

强大的多合一题目

精确地数学推导和耐心。

有套路又不失心意。

融合了：

算法：

prufer序列及其扩展

树形Dp

容斥或者二项式定理

EGF

多项式Exp

先要会：

省选模拟赛第四轮 B——O(n^4)->O(n^3)->O(n^2)

然后开始刚题。

就是：

求各种情况下的y^(n-|T1∩T2|)的和

OP=0

哈希。

OP=1

枚举交集，统计符合的T2树的个数

prufer序列森林版扩展

但是会算重，连回去会多

考虑重组贡献

每个实际的$y^k$会被$k$小的时候计算，$y^k=(y+1-1)^k=∑C(j,i)(y-1)^i$

发现，只要把贡献的$y$成$y-1$，就大功告成啦！

$\Pi szi$可以套路地组合意义成为每个连通块选择一个的方案数，然后就$f[i][0/1]$就O(n)辣

注意每次选择交的边还有贡献

[WC2019] 数树

这里，第二个$y^{-1}$运算的时候，要变成$(y^{-1}-1)$

OP=2

还是枚举交集的边

发现和交集大小密切相关，所以枚举交集大小$s$

然后$gs$设出来，

要枚举边再考虑连通块，不妨枚举连通块考虑贡献的边集

连通块的分配$\frac{n!}{(n-s)!}$,连通块内的连边$a^{a-2}$，连通块之间连边$\Pi a_i *n^{m-2}$

一些东西要平方

把$gs$带回去，然后无关的都提到前面去

把枚举连通块，变成EGF

然后再变成多项式指数函数的形式，大功告成！

[WC2019] 数树

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Miracle{

const int N=1e5+;

const int mod=;

const int G=;

const int GI=;

int n,Y;

int mul(int x,int y){return (ll)x*y%mod;}

int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}

il int sub(int x,int y){return ad(x,mod-y);}

int qm(int x,int y){

    int ret=;

    while(y){

        if(y&) ret=mul(ret,x);

        x=mul(x,x);

        y>>=;

    }

    return ret;

}

namespace sol0{

map<pair<int,int>,int>mp;

int cnt;

void main(){

    int x,y;

    for(reg i=;i<n;++i){

        rd(x);rd(y);if(x>y) swap(x,y);mp[mk(x,y)]=;

    }

    for(reg i=;i<n;++i){

        rd(x);rd(y);if(x>y) swap(x,y);cnt+=mp[mk(x,y)];

    }

    printf("%d\n",qm(Y,n-cnt));

}

}

namespace sol1{

ll f[N][];

int z;

int cos,ivc;

struct node{

    int nxt,to;

}e[*N];

int hd[N],cnt;

void add(int x,int y){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    hd[x]=cnt;

}

void dfs(int x,int fa){

    f[x][]=f[x][]=;

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        dfs(y,x);

        //jiao and no

        ll od0=f[x][],od1=f[x][];

        f[x][]=ad(mul(od0,f[y][]),mul(od0,mul(f[y][],cos)));

        f[x][]=ad(mul(od1,f[y][]),ad(mul(od0,mul(f[y][],cos)),mul(od1,mul(f[y][],cos))));

    }

}

void main(){

    int x,y;

    for(reg i=;i<n;++i){

        rd(x);rd(y);add(x,y);add(y,x);

    }

    if(Y==){

        printf("%d\n",qm(n,n-));

        return;

    }

    z=ad(qm(Y,mod-),mod-);

    cos=mul(z,qm(n,mod-));

    ivc=qm(cos,mod-);

//    cout<<" cos "<<cos<<" ivc "<<ivc<<endl;

    dfs(,);

    ll ans=;

    ans=mul(mul(qm(n,n-),qm(Y,n)),f[][]);

    cout<<ans;

}

}

namespace sol2{

struct Poly{

    vector<int>f;

    Poly(){f.clear();}

    il int &operator[](const int &x){return f[x];}

    il const int &operator[](const int &x) const {return f[x];}

    il void resize(const int &n){f.resize(n);}

    il int size() const {return f.size();}

    il void cpy(Poly &b){f.resize(b.size());for(reg i=;i<(int)f.size();++i)f[i]=b[i];}

    il void rev(){reverse(f.begin(),f.end());}

    il void clear(){f.clear();}

    il void read(const int &n){f.resize(n);for(reg i=;i<n;++i)rd(f[i]);}

    il void out() const {for(reg i=;i<(int)f.size();++i)ot(f[i]);putchar('\n');}

}R;

il int init(const int &n){int m;for(m=;m<n;m<<=);return m;}

il void rev(Poly &f){

    int lp=f.size();

    if(R.size()!=f.size()) {

        R.resize(f.size());

        for(reg i=;i<lp;++i){

            R[i]=(R[i>>]>>)|((i&)?lp>>:);

        }

    }

    for(reg i=;i<lp;++i){

        if(i<R[i]) swap(f[i],f[R[i]]);

    }

}

il void NTT(Poly &f,int c){

    int n=f.size();rev(f);

    for(reg p=;p<=n;p<<=){

        int gen=(c==)?qm(G,(mod-)/p):qm(GI,(mod-)/p);

        for(reg l=;l<n;l+=p){

            int buf=;

            for(reg k=l;k<l+p/;++k){

                int tmp=mul(f[k+p/],buf);

                f[k+p/]=sub(f[k],tmp);

                f[k]=ad(f[k],tmp);

                buf=mul(buf,gen);

            }

        }

    }

    if(c==-){

        int iv=qm(n,mod-);for(reg i=;i<n;++i) f[i]=mul(f[i],iv);

    }

}

il Poly Inv(const Poly &f,int n){

    if(n==){

        Poly g;g.resize();g[]=qm(f[],mod-);return g;

    }

    Poly g=Inv(f,(n+)>>),t;

    int m=init(n*);

    t.resize(m);

    for(reg i=;i<n;++i)t[i]=f[i];

    g.resize(m);

    NTT(g,);NTT(t,);

    for(reg i=;i<m;++i)g[i]=mul(sub(,mul(g[i],t[i])),g[i]);

    NTT(g,-);g.resize(n);

    return g;

}

il void operator *=(Poly &f,Poly g){

    int st=f.size()+g.size()-;

    int len=init(f.size()+g.size()-);f.resize(len);g.resize(len);

    NTT(f,);NTT(g,);for(reg i=;i<len;++i) f[i]=mul(f[i],g[i]);

    NTT(f,-);

    f.resize(st);

}

il void operator *=(Poly &f,const int &c){for(reg i=;i<f.size();++i) f[i]=mul(f[i],c);}

il Poly operator *(Poly f,const Poly &g){f*=g;return f;}

il Poly operator *(Poly f,const int &c){for(reg i=;i<f.size();++i) f[i]=mul(f[i],c);return f;}

il void operator +=(Poly &f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=ad(f[i],g[i]);}

il void operator +=(Poly &f,const int &c){f[]=ad(f[],c);}

il Poly operator +(Poly f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=ad(f[i],g[i]);return f;}

il Poly operator +(Poly f,const int &c){f[]=ad(f[],c);return f;}

il void operator -=(Poly &f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=sub(f[i],g[i]);}

il void operator -=(Poly &f,const int &c){f[]=sub(f[],c);}

il Poly operator -(Poly f,const Poly &g){for(reg i=;i<f.size();++i) f[i]=sub(f[i],g[i]);return f;}

il Poly operator -(Poly f,const int &c){f[]=sub(f[],c);return f;}

il Poly operator ~(const Poly &f){return Inv(f,f.size());}

il Poly operator /(Poly f,Poly g){int len=f.size()-g.size()+;f.rev();g.rev();g.resize(len);f=f*(~g);f.resize(len);f.rev();return f;}

il Poly operator %(Poly f,Poly g){Poly s=f/g;f=f-g*s;f.resize(g.size()-);return f;}

il Poly Inter(Poly f){int st=f.size();f.resize(st+);for(reg i=st;i>=;--i){f[i]=mul(f[i-],qm(i,mod-));}f[]=;return f;}

il Poly Diff(Poly f){int st=f.size();for(reg i=;i<st-;++i) f[i]=mul(f[i+],(i+));f.resize(st-);return f;}

il Poly Ln(const Poly &f){Poly g=Diff(f),h=(~f);g=g*h;g.resize(f.size()-);return Inter(g);}

il Poly Exp(const Poly &f,int n){

    if(n==){

        Poly g;g.resize();g[]=;

        return g;

    }

    Poly g=Exp(f,(n+)>>);

    g.resize(n);

    g=g*(((Ln(g)*(mod-))+)+f);

    g.resize(n);

    return g;

}

il Poly Exp(const Poly &f){

    return Exp(f,f.size());

}

int jie[N],inv[N];

void main(){

    if(Y==){

        printf("%d\n",mul(qm(n,n-),qm(n,n-)));

        return;

    }

    int z=ad(qm(Y,mod-),mod-);

    Poly g;

    g.resize(n+);

    int ivz=qm(z,mod-);

    jie[]=;

    for(reg i=;i<=n;++i) jie[i]=mul(jie[i-],i);

    inv[n]=qm(jie[n],mod-);

    for(reg i=n-;i>=;--i) inv[i]=mul(inv[i+],i+);

    for(reg j=;j<=n;++j){

        g[j]=mul(mul(mul(mul(n,n),ivz),inv[j]),qm(j,j));

    }

    g=Exp(g);

    ll ans=mul(mul(mul(mul(qm(Y,n),jie[n]),qm(qm(n,mod-),)),qm(z,n)),g[n]);

    cout<<ans;

}

}

int main(){

    int op;

    rd(n);rd(Y);rd(op);

    if(op==) sol0::main();

    else if(op==) sol1::main();

    else sol2::main();

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/4/12 15:09:42

*/

前言

OP=0

OP=1

OP=2

相关文章