题目概述

HDU5279

解题报告

首先每个连通块里必须是森林，然后连接每个连通块的 $n$ 条边只要删掉一条，就肯定不会存在全局环，这样每个连通块就独立了。

定义 $f_i$ 表示 $i$ 个点树的方案数，则 $f_0=0,f_i=i^{i-2}$ 。

定义 $g_i$ 表示 $i$ 个点森林的方案数，考虑指数型生成函数，则易知 $G(x)=e^{F(x)}$ 。

但是这样有一种情况没有考虑到，即 $n$ 条边一条都没删，但是至少存在一个连通块，$1$ 和 $a_i$ 点是不连通的，这样也不存在全局环。

定义 $h_i$ 表示 $i$ 个点，$1$ 和 $i$ 不连通的森林方案数，根据套路，枚举 $1$ 所在树，则：

$$ h_1=0,h_i=\sum_{j=1}^{i-1}{i-2\choose j-1}f_jg_{i-j}=\sum_{j=1}^{i-1}(i-2)!{f_j\over (j-1)!}{g_{i-j}\over (i-j-1)!} $$

$h$ 可以通过 $f$ 和 $g$ 卷积得到，因此答案为：

$$ 2^n\prod_{i=1}^{n}g_{a_i}-\prod(g_{a_i}-h_{a_i}) $$

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=1<<18,MOD=998244353;

int te,n,a[maxn+5],INV[maxn+5],fac[maxn+5];
int wn[maxt+5],temA[maxt+5],temB[maxt+5],F[maxt+5],G[maxt+5],H[maxt+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
__attribute__((constructor)) void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
    INV[0]=INV[1]=1;for (int i=2;i<=maxn;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    fac[0]=1;for (int i=1;i<=maxn;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Inte(int *F,int *a,int n,int K){ // F=integral(a)
    for (int i=n+K;i>=K;i--) F[i]=MUL(a[i-K],MUL(INV[i],fac[i-K]));
    for (int i=0;i<K;i++) F[i]=0;
}
void Deri(int *F,int *a,int n,int K){ // F=a'
    for (int i=0;i<=n-K;i++) F[i]=MUL(a[i+K],MUL(fac[i+K],INV[i]));
    for (int i=n-K+1;i<=n;i++) F[i]=0;
}
void Inv(int *F,int *a,int n){ // F=1/a
    if (n==1) {F[0]=Pow(a[0],MOD-2);return;}
    Inv(F,a,n>>1);
    for (int i=0;i<n;i++) temA[i]=a[i],temA[i+n]=F[i+n]=0;
    NTT(temA,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(F[i],2+MOD-MUL(temA[i],F[i]));
    NTT(temA,n<<1,-1);for (int i=0;i<n;i++) F[i]=temA[i],F[i+n]=0;
}
void Ln(int *F,int *a,int n){ // F=ln(a)
    Inv(temB,a,n);
    Deri(temA,a,n-1,1);for (int i=0;i<n;i++) temA[i+n]=0;
    NTT(temA,n<<1,1);NTT(temB,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(temA[i],temB[i]);
    NTT(temA,n<<1,-1);Inte(F,temA,n-2,1);
}
void Exp(int *F,int *a,int n){ // F=exp(a)
    if (n==1) {F[0]=1;return;} // only when a[0]=0
    Exp(F,a,n>>1);Ln(temA,F,n);
    for (int i=0;i<n;i++) temA[i]=ADD(a[i],MOD-temA[i]),temA[i+n]=F[i+n]=0;
    temA[0]=ADD(temA[0],1);
    NTT(temA,n<<1,1);NTT(F,n<<1,1);
    for (int i=0;i<(n<<1);i++) temA[i]=MUL(temA[i],F[i]);
    NTT(temA,n<<1,-1);for (int i=0;i<n;i++) F[i]=temA[i],F[i+n]=0;
}
int main(){
    F[1]=1;for (int i=2;i<=maxn;i++) F[i]=MUL(Pow(i,i-2),INV[i]);
    Exp(G,F,maxt>>1);
    G[0]=0;for (int i=1;i<=maxn;i++) G[i]=MUL(G[i],fac[i]),F[i]=MUL(F[i],fac[i]);
    for (int i=maxn+1;i<maxt;i++) G[i]=0;
    for (int i=1;i<=maxn;i++) F[i]=MUL(F[i],INV[i-1]),G[i]=MUL(G[i],INV[i-1]);
    NTT(F,maxt,1);NTT(G,maxt,1);
    for (int i=0;i<maxt;i++) H[i]=MUL(F[i],G[i]);
    NTT(H,maxt,-1);NTT(F,maxt,-1);NTT(G,maxt,-1);
    for (int i=1;i<=maxn;i++){
        F[i]=MUL(F[i],fac[i-1]);G[i]=MUL(G[i],fac[i-1]);
        if (i>1) H[i]=MUL(H[i],fac[i-2]);
    }
    for (scanf("%d",&te);te;te--){
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        int ans=Pow(2,n),pre=1;
        for (int i=1;i<=n;i++) ans=MUL(ans,G[a[i]]),pre=MUL(pre,ADD(G[a[i]],MOD-H[a[i]]));
        printf("%d\n",ADD(ans,MOD-pre));
    }
    return 0;
}