Codechef Chef Cuts Tree

该思博的时候就思博到底，套路的时候不能再套路的一道题

首先我们将联通块的大小平方和进行转化，发现它就等价于连通点对数，而这个可以转化为连接两点的边数（距离）和

所以我们考虑第\(i\)天时，一个点对\((x,y)\)能产生贡献，当且仅当连接它们的边一条都没断，故贡献为：

\[\frac{(n-1-\operatorname{dis}(x,y))^{\underline i}}{(n-1)^{\underline i}}\]

因此我们发现这个东西对于所有距离相同的点对是一样的，因此我们可以直接统计出所有的距离为\(i(i\in[0,n-1])\)的点对数\(num_i\)

然后考虑对于一天\(i\)枚举距离为\(d\)的点对，则：

\[ans_i=\sum_{d=0}^{n-1}\frac{(n-d-1)!\times(n-i-1)!\times num_d}{(n-d-i-1)!\times(n-1)!}\]

显然是一个卷积的形式，我们令\(A(x)=(n-i-1)!\times num_i,B(x)=\frac{1}{i!}\)，卷积之后乘回不变项然后反转即可

那么剩下还有两个问题，距离为\(i\)的点对数怎么求？

首先一眼点分治，然后有一个很naive的想法就是遍历每颗子树信息后暴力FFT合并

但这样遇到菊花图就直接GG了，因此我们可以容斥一下

每次以分治中心为根找出所有长度的路径条数，然后卷积平方后减去重复在同一子树内的部分即可，计算方法和之前一致

最后一个问题，模数不是NTT模数毒瘤出题人，难不成我们写三模NTT？

然而发现之前FFT已经写好了，因此我们直接拆系数做就好了

PS：本人太弱不会MTT，因此写了最暴力的4次DFT，4次IDFT的大常数版本，复杂度就当作两只\(\log\)来看吧

最后跑了1.36s，注意开long long和long double

CODE

#include<cstdio>
#include<cctype>
#include<iostream>
#include<cmath>
#define int LL
#define RI register int
#define CI const int&
#define Tp template <typename T>
#define CC const Complex&
using namespace std;
typedef long long LL;
const int N=200005,INF=1e9,mod=1e9+7;
const long double pi=acos(-1);
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[15];
    public:
        inline FileInputOutput() { Ftop=Fout; Fend=Fout+S; }
        Tp inline void read(T& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        Tp inline void write(T x)
        {
            RI ptop=0; while (pt[++ptop]=x%10,x/=10);
            while (ptop) pc(pt[ptop--]+48); pc(' ');
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
        #undef tc
        #undef pc
}F;
struct Complex
{
    long double x,y;
    inline Complex(const long double& X=0,const long double& Y=0)
    {
        x=X; y=Y;
    }
    friend inline Complex operator + (CC A,CC B)
    {
        return Complex(A.x+B.x,A.y+B.y);
    }
    friend inline Complex operator - (CC A,CC B)
    {
        return Complex(A.x-B.x,A.y-B.y);
    }
    friend inline Complex operator * (CC A,CC B)
    {
        return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
    }
    inline void operator /= (const long double& p)
    {
        x/=p; y/=p;
    }
}A[N<<2]; int a[N<<2],ans[N<<2],fact[N],inv[N];
struct edge
{
    int to,nxt;
}e[N<<1]; int n,head[N],cnt,x,y,dis[N],lim;
class FFT_Solver
{
    private:
        static const int S=ceil(sqrt(mod)),SS=1LL*S*S%mod;
        int rev[N<<2],p;
    public:
        inline void init(CI n)
        {
            for (lim=1,p=0;lim<=n;lim<<=1,++p);
            for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
        }
        inline void FFT(Complex *f,CI opt)
        {
            RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
            for (i=1;i<lim;i<<=1)
            {
                Complex D(cos(pi/i),sin(pi/i)*opt);
                for (RI j=0;j<lim;j+=(i<<1))
                {
                    Complex W(1,0); for (RI k=0;k<i;++k,W=W*D)
                    {
                        Complex x=f[j+k],y=f[i+j+k]*W;
                        f[j+k]=x+y; f[i+j+k]=x-y;
                    }
                }
            }
            if (!~opt) for (i=0;i<lim;++i) f[i]/=lim;
        }
        inline void MTT(int *TA,int *TB,int *TC,CI n)
        {
            static Complex A[N<<2],B[N<<2],C[N<<2],D[N<<2],E[N<<2],F[N<<2],G[N<<2],H[N<<2];
            RI i; for (init(n<<1),i=0;i<n;++i)
            A[i]=Complex(TA[i]/S),B[i]=Complex(TA[i]%S),C[i]=Complex(TB[i]/S),D[i]=Complex(TB[i]%S);
            for (FFT(A,1),FFT(B,1),FFT(C,1),FFT(D,1),i=0;i<lim;++i)
            E[i]=A[i]*C[i],F[i]=B[i]*C[i],G[i]=A[i]*D[i],H[i]=B[i]*D[i];
            for (FFT(E,-1),FFT(F,-1),FFT(G,-1),FFT(H,-1),i=0;i<lim;++i)
            TC[i]=(((LL)(E[i].x+0.5)%mod)*SS)%mod,(TC[i]+=(((LL)(F[i].x+0.5)%mod)*S)%mod)%=mod,
            (TC[i]+=(((LL)(G[i].x+0.5)%mod)*S)%mod)%=mod,(TC[i]+=(LL)(H[i].x+0.5)%mod)%=mod;
        }
}P;
#define to e[i].to
class Point_Divide_Solver
{
    private:
        int size[N],mx[N],num[N],rt,ats,mdp; bool vis[N];
        inline void maxer(int& x,CI y)
        {
            if (y>x) x=y;
        }
        inline void getrt(CI now=1,CI fa=0)
        {
            size[now]=1; mx[now]=0; for (RI i=head[now];i;i=e[i].nxt)
            if (to!=fa&&!vis[to]) getrt(to,now),size[now]+=size[to],maxer(mx[now],size[to]);
            if (maxer(mx[now],ats-size[now]),mx[now]<mx[rt]) rt=now;
        }
        inline void travel(CI now,CI fa=0,CI dep=0)
        {
            maxer(mdp,dep); ++num[dep]; for (RI i=head[now];i;i=e[i].nxt)
            if (to!=fa&&!vis[to]) travel(to,now,dep+1);
        }
        inline void calc(CI opt)
        {
            RI i; for (P.init(mdp<<1),i=0;i<=mdp;++i) A[i]=Complex(num[i],0);
            for (i=mdp+1;i<lim;++i) A[i]=Complex();
            for (P.FFT(A,1),i=0;i<lim;++i) A[i]=A[i]*A[i];
            for (P.FFT(A,-1),lim=min(n-1,mdp<<1),i=0;i<=lim;++i)
            dis[i]+=(LL)(A[i].x+0.5)%mod*opt,(dis[i]+=mod)%=mod;
        }
        inline void clear(void)
        {
            for (RI i=0;i<=mdp;++i) num[i]=0;
        }
        inline void solve(CI now)
        {
            RI i; mdp=0; travel(now); calc(1); clear(); vis[now]=1;
            for (i=head[now];i;i=e[i].nxt) if (!vis[to])
            mdp=0,travel(to,now,1),calc(-1),clear();
            for (i=head[now];i;i=e[i].nxt) if (!vis[to])
            mx[rt=0]=INF,ats=size[to],getrt(to,now),solve(rt);
        }
    public:
        inline void divide(void)
        {
            mx[rt=0]=INF; ats=n; getrt(); solve(rt);
        }
}PD;
#undef to
inline void addedge(CI x,CI y)
{
    e[++cnt]=(edge){y,head[x]}; head[x]=cnt;
    e[++cnt]=(edge){x,head[y]}; head[y]=cnt;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
    for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(void)
{
    RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
    for (inv[n]=quick_pow(fact[n]),i=n-1;~i;--i) inv[i]=1LL*inv[i+1]*(i+1)%mod;
    for (i=0;i<n;++i) a[i]=1LL*fact[n-i-1]*dis[i]%mod;
    //for (i=0;i<n;++i) printf("%d ",a[i]); putchar('\n');
    //for (i=0;i<n;++i) printf("%d ",inv[i]); putchar('\n');
}
signed main() 
{
    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
    RI i; for (F.read(n),i=1;i<n;++i) F.read(x),F.read(y),addedge(x,y);
    for (PD.divide(),init(),P.MTT(a,inv,ans,n),i=0;i<n;++i)
    ans[n-i-1]=1LL*ans[n-i-1]*inv[n-1]%mod*fact[n-i-1]%mod;
    for (i=0;i<n;++i) F.write(ans[n-i-1]); return F.flush(),0;
}

Codechef Chef Cuts Tree

原文：https://www.cnblogs.com/cjjsb/p/11285742.html