HDU 5279 分治NTT 图的计数

思路：

显然每个子图内都是森林

去掉所有子图1和n都连通且每条大边都存在的情况

直接DP上

NTT优化一波

注意前两项的值..

//By SiriusRen

#include <bits/stdc++.h>

using namespace std;

const int mod=,N=;

int cases,n,R[N],fac[N],inv[N],A[N],B[N],h[N],f[N],g[N],jy;

int power(int x,int y){

    int r=;

    while(y){

        if(y&)r=1ll*x*r%mod;

        x=1ll*x*x%mod,y>>=;

    }return r;

}

void NTT(int *a,int f,int m){

    int L=,n;

    for(n=;n<m;n<<=)L++;

    for(int i=;i<n;i++)R[i]=(R[i>>]>>)|((i&)<<(L-));

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

    for(int l=;l<n;l<<=){

        int wn=power(,((mod-)/(l<<)*f+(mod-))%(mod-));

        for(int j=;j<n;j+=(l<<)){

            int w=;

            for(int k=;k<l;k++,w=1ll*w*wn%mod){

                int x=a[j+k],y=1ll*w*a[j+k+l]%mod;

                a[j+k]=(x+y)%mod,a[j+k+l]=(x-y+mod)%mod;

            }

        }

    }

    if(f==-){

        int ni=power(n,mod-);

        for(int i=;i<n;i++)a[i]=1ll*a[i]*ni%mod;

    }

}

void cdq(int l,int r){

    if(l==r){

        if(l==)f[l]=;

        else f[l]=(1ll*f[l]*fac[l-]+1ll*h[l]*fac[l-])%mod;

        return;

    }

    int mid=(l+r)>>;

    cdq(l,mid);

    int len1=mid-l+,len2=r-l+,len=;

    while(len<len1+len2)len<<=;

    for(int i=;i<len1;i++)A[i]=1ll*f[l+i]*inv[l+i]%mod;

    for(int i=len1;i<len;i++)A[i]=;

    for(int i=;i<len2;i++)B[i]=h[i];

    for(int i=len2;i<len;i++)B[i]=;

    NTT(A,,len),NTT(B,,len);

    for(int i=;i<len;i++)A[i]=1ll*A[i]*B[i]%mod;

    NTT(A,-,len);

    for(int i=mid+;i<=r;i++)f[i]=(f[i]+A[i-l])%mod;

    cdq(mid+,r);

}

void init(){

    fac[]=h[]=;

    for(int i=;i<=;i++)fac[i]=1ll*fac[i-]*i%mod;

    inv[]=power(fac[],mod-);

    for(int i=;~i;i--)inv[i]=1ll*inv[i+]*(i+)%mod;

    for(int i=;i<=;i++)h[i]=1ll*power(i,i-)*inv[i-]%mod;

    cdq(,),f[]=;

    for(int i=;i<;i++)A[i]=B[i]=;

    for(int i=;i<=;i++)A[i]=1ll*f[i]*inv[i]%mod;

    B[]=B[]=;

    for(int i=;i<=;i++)B[i]=1ll*h[i]*(i-)%mod;

    NTT(A,,),NTT(B,,);

    for(int i=;i<;i++)g[i]=1ll*A[i]*B[i]%mod;

    NTT(g,-,),g[]=;

    for(int i=;i<=;i++)g[i]=1ll*g[i]*fac[i-]%mod;

}

int main(){

    scanf("%d",&cases),init();

    while(cases--){

        scanf("%d",&n);int a1=,a2=;

        for(int i=;i<=n;i++)scanf("%d",&jy),a1=1ll*a1*f[jy]%mod,a2=1ll*a2*g[jy]%mod;

        printf("%lld\n",(1ll*a1*power(,n)%mod-a2+mod)%mod);

    }

}