自动搬运

查看原文

来自洛谷，原作者为

	Panda_hu [已AFO]这个家伙不懒，但是什么也没能留下

搬运于2025-08-24 22:14:43，当前版本为作者最后更新于2020-07-08 17:38:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

点此查看全文

求 $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()));
}