题解 P5827 【点双连通图计数】

· · 题解

点此查看全文

求 n 个点的有标号点双连通图（简单无向图，整个图是一个点双连通分量）的个数，答案对 998244353 取模。

点双连通图:如果一个无向连通图删去任意一个点都仍然是连通的，我们就称其为点双连通图。

首先我们需要明确一点:对于一个无向简单连通图，任意一个点必定在至少一个点双连通分量里面，一个点双连通分量的大小至少大于等于2。

所以我们首先需要特判n=1的情况。

我们先用上一道题的做法求出i个点无向连通图数生成函数F(x)。

然后设i个点有根无向连通图数d_i的生成函数为D(x)，i个点无根点双连通图数b_i的生成函数为B(x)。

显然可以得到[x^n]D(x)=n[x^n]F(x)。

考虑如何得到B(x)和F(x)之间的关系，我们可以利用我们一开始知道的性质，那么对于一个有根无向连通图其选中的根必定在至少一个点双连通分量里面，而且根据定义这些点双连通分量两两的交集有且只有根

例如下面这个奇怪的有根无向连通图，包含它的根R的点双连通分量的点集可以表示为\{3,R\},\{4,5,6,7,8,R\},\{9,10,11,12,R\}。

如何计数？现在我们考虑先将R这个点与其相邻的边删去。

显然现在的连通块个数为先前包含根的点双连通分量的个数，我们对于每一个连通块单独计数，由于这些连通块理论上没有任何块数限制且相互独立，因此把它们exp起来即可。

观察\{3,R\}这一组点双连通分量我们可以发现，对于每一个在点双连通分量上的点(除去R)我们其实都可以在上面插上一个以其为根的无向连通图，并且容易发现这样做并不会影响到包含这个根R的任何点双连通分量的大小。

那么很容易得到一个连通块的方案数的生成函数:

\sum^{∞}_{i=1}b_{i+1}\frac{D^i(x)}{i!}

注意到\sum^{∞}_{i=1}\frac{b_{i+1}}{i!}x^i就为B'(x)，因此原式等于B'(D(x))。

那么整个图的生成函数为D(x)=xe^{B'(D(x))}(注意加上根)。

现在我们成功的找到了D(x)与B(x)的关系，然而这个式子并不能牛顿迭代，考虑用复合逆解决:

B'(D(x))=\ln \frac{D(x)}{x}

令H(x)=\ln \frac{D(x)}{x}，套扩展拉格朗日反演公式可以得到:

[x^n]B'(x)=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{D(x)})^n

由定义得e^{-H(x)}=\frac{x}{D(x)}，因此:

[x^n]B'(x)=\frac{1}{n}[x^{n-1}]H'(x)e^{-nH(x)}

注意我们求到的是B'(x)的系数，因此强烈建议一开始就将n减一然后做一遍(上面的推导也是减了一的)，最后再乘以一个(n-1)!(这里的n是减了之后的,由于B(x)是EGF我们首先乘(n+1)!,因为求导除以(n+1),由于上面反演有一个系数再除一次n)。

理论复杂度:O(n\log n)(常数巨大)。

实现

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;

#define LL long long
#define DB double
#define MAXN 600000
#define MOD 998244353
#define G 3
#define Pr pair<LL,int>
#define X first
#define Y second
#define INF 1000000000000000000
#define mem(x,v) memset(x,v,sizeof(x))

LL read(){
    LL x=0,F=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x*10+c-'0')%MOD;c=getchar();}
    return x*F;
}
int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return (1LL*a*b)%MOD;}
int fst_pow(int a,LL b){
    int res=1;
    while(b){
        if(b&1)res=mul(res,a);
        a=mul(a,a),b>>=1;
    }return res;
}

int inv2,fac[MAXN+5],ifac[MAXN+5];

void prepare(){
    fac[0]=1;
    for(int i=1;i<=MAXN;i++)fac[i]=mul(fac[i-1],i);
    ifac[MAXN]=fst_pow(fac[MAXN],MOD-2);
    for(int i=MAXN;i>=1;i--)ifac[i-1]=mul(ifac[i],i);
}
void NTT(int *a,int n,int x){
    for(int i=0,j=0;i<n;i++){
        if(i<j)swap(a[i],a[j]);
        int k=n>>1;
        while(k&&(k&j))j^=k,k>>=1;
        j^=k;
    }
    for(int i=1;i<n;i<<=1){
        int gn=fst_pow(G,(MOD-1)/(i<<1));
        for(int j=0;j<n;j+=(i<<1)){
            int g=1;
            for(int k=0;k<i;k++,g=mul(g,gn)){
                int X=a[j+k],Y=mul(a[i+j+k],g);
                a[j+k]=add(X,Y),a[i+j+k]=dec(X,Y);
            }
        }
    }
    if(x==1)return ;
    int ny=fst_pow(n,MOD-2);reverse(a+1,a+n);
    for(int i=0;i<n;i++)a[i]=mul(a[i],ny);
}
void ploy_inv(int n,int *a,int *b){
    static int c[MAXN+5];
    if(n==1){b[0]=fst_pow(a[0],MOD-2);return ;}
    ploy_inv((n+1)>>1,a,b);
    int len=1;
    while(len<(n<<1))len<<=1;
    copy(a,a+len,c);
    fill(c+n,c+len,0),NTT(c,len,1);
    fill(b+n,b+len,0),NTT(b,len,1);
    for(int i=0;i<len;i++)
    b[i]=mul(dec(2,mul(c[i],b[i])),b[i]);
    NTT(b,len,-1);
    fill(b+n,b+len,0);
}
void ploy_der(int n,int *a,int *b){
    for(int i=1;i<n;i++)b[i-1]=mul(a[i],i);
    b[n-1]=0;
}
void ploy_cal(int n,int *a,int *b){
    for(int i=1;i<n;i++)b[i]=mul(a[i-1],fst_pow(i,MOD-2));
    b[0]=0;
}
void ploy_ln(int n,int *a,int *b){
    static int A[MAXN+5],B[MAXN+5];
    fill(A,A+(n<<1),0),fill(B,B+(n<<1),0);
    ploy_der(n,a,A),ploy_inv(n,a,B);
    int len=1;while(len<(n<<1))len<<=1;
    NTT(A,len,1),NTT(B,len,1);
    for(int i=0;i<len;i++)A[i]=mul(A[i],B[i]);
    NTT(A,len,-1),ploy_cal(n,A,b);
}
void ploy_exp(int n,int *a,int *b){
    static int F[MAXN+5];
    if(n==1){b[0]=1;return ;}
    ploy_exp((n+1)>>1,a,b);
    fill(F,F+(n<<1),0),ploy_ln(n,b,F);
    for(int i=0;i<n;i++)F[i]=dec(a[i],F[i]);
    F[0]=add(F[0],1);
    int len=1;while(len<(n<<1))len<<=1;
    fill(b+n,b+len,0),NTT(b,len,1);
    fill(F+n,F+len,0),NTT(F,len,1);
    for(int i=0;i<len;i++)b[i]=mul(b[i],F[i]);
    NTT(b,len,-1),fill(b+n,b+len,0);
}
int n,m,f[MAXN+5],g[MAXN+5],h[MAXN+5],dh[MAXN+5],tmp[MAXN+5],nh[MAXN+5];
void init(){
    m=1<<17;
    for(int i=0;i<m;i++)f[i]=mul(fst_pow(2,1LL*i*(i-1)/2%(MOD-1)),ifac[i]);
    ploy_ln(m,f,g);
    for(int i=0;i<m-1;i++)g[i]=mul(g[i+1],i+1);
    g[m-1]=0;
    ploy_ln(m,g,h);
    ploy_der(m,h,dh);
    NTT(dh,m<<1,1);
}
int solve(int n){
    n--;
    if(!n)return 1;
    for(int i=m;i<(m<<1);i++)tmp[i]=0;
    for(int i=0;i<m;i++)tmp[i]=mul(h[i],MOD-n);
    ploy_exp(m,tmp,nh);
    NTT(nh,m<<1,1);
    for(int i=0;i<(m<<1);i++)nh[i]=mul(nh[i],dh[i]);
    NTT(nh,m<<1,-1);
    return mul(nh[n-1],fac[n-1]);
}

int main(){
    prepare(),init();
    for(int i=1;i<=5;i++)
    printf("%d\n",solve(read()));
}