如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
边双联通图计数
前置知识：无向联通图计数，扩展拉格朗日反演。
无向联通图计数
设 $F(x)$ 为有标号无向图的 $\text{EGF}$，$G(x)$ 为有标号无向联通图的 $\text{EGF}$，根据 $\exp$ 的组合意义有 $F=\exp G$，所以有 $G=\ln F$，$F(x)=\sum\limits_{i=0}^\infin\frac{2^{i\choose 2}x^i}{i!}$。
边双联通图计数
设有根有标号无向联通图的 $\text{EGF}$ 为 $D(x)$，显然有 $[x^n]D(x)=n[x^n]G(x)$。设有根有标号边双联通图的 $\text{EGF}$ 为 $B(x)$，注意到一个有根无向图一定是由根所在的边双向外连了一些无向图构成的，即
\[D(x)=\sum\limits_{i=1}^\infin\frac{b_ix^i\exp(iD(x))}{i!}=B(x\exp(D(x)))\]设 $F(x)=x\exp(D(x))$，则 $D(x)=B(F(x))$，两边对 $F(x)$ 作复合逆，则有 $B(x)=D(F^{-1}(x))$，由扩展拉格朗日反演得 $[x^n]B(x)=\frac{1}{n}[x^{n-1}] (D’(x)(\frac{x}{F(x)})^n)$ ，化简得：
\[[x^n]B(x)=\frac{1}{n}[x^{n-1}](D'(x)\exp(-nD(x)))\]#include<cstdio>
#include<algorithm>
int const mod=998244353,g=3,gi=998244354/3,maxn=400010;
int pow(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*x*res%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
struct NTT{
int r[maxn],lim;
NTT():r(),lim(){}
void getr(int lm){
lim=lm;
for(int i=0;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
void operator ()(int *a,int type){
for(int i=0;i<lim;i++)if(i<r[i])std::swap(a[i],a[r[i]]);
for(int mid=1;mid<lim;mid<<=1){
int rt=pow(type==1?g:gi,(mod-1)/(mid<<1));
for(int r=mid<<1,j=0;j<lim;j+=r){
int p=1;
for(int k=0;k<mid;k++,p=1ll*p*rt%mod){
int x=a[j+k],y=1ll*p*a[j+mid+k]%mod;
a[j+k]=(x+y)%mod,a[j+mid+k]=(x-y+mod)%mod;
}
}
}
if(type==-1)for(int i=0,p=pow(lim,mod-2);i<lim;i++)a[i]=1ll*p*a[i]%mod;
}
}ntt;
void inv(int const *a,int *ans,int n){
static int tmp[maxn];
for(int i=0;i<n<<1;i++)tmp[i]=ans[i]=0;
ans[0]=pow(a[0],mod-2);
for(int m=2;m<=n;m<<=1){
int lim=m<<1;
ntt.getr(lim);
for(int i=0;i<m;i++)tmp[i]=a[i];
ntt(tmp,1),ntt(ans,1);
for(int i=0;i<lim;i++)ans[i]=ans[i]*(2-1ll*ans[i]*tmp[i]%mod+mod)%mod,tmp[i]=0;
ntt(ans,-1);
for(int i=m;i<lim;i++)ans[i]=0;
}
}
void inte(int const *a,int *ans,int n){
for(int i=n-1;i;i--)ans[i]=1ll*a[i-1]*pow(i,mod-2)%mod;
ans[0]=0;
}
void der(int const *a,int *ans,int n){
for(int i=1;i<n;i++)ans[i-1]=1ll*i*a[i]%mod;
ans[n-1]=0;
}
void ln(int const *a,int *ans,int n){
static int b[maxn];
for(int i=0;i<n<<1;i++)ans[i]=b[i]=0;
inv(a,ans,n);
der(a,b,n);
int lim=n<<1;
ntt.getr(lim);
ntt(b,1),ntt(ans,1);
for(int i=0;i<lim;i++)b[i]=1ll*ans[i]*b[i]%mod,ans[i]=0;
ntt(b,-1);
for(int i=n;i<lim;i++)b[i]=0;
inte(b,ans,n);
}
void exp(int const *a,int *ans,int n){
static int f[maxn];
for(int i=0;i<n<<1;i++)ans[i]=f[i]=0;
ans[0]=1;
for(int m=2;m<=n;m<<=1){
int lim=m<<1;
ln(ans,f,m);
f[0]=(a[0]+1-f[0]+mod)%mod;
for(int i=1;i<m;i++)f[i]=(a[i]-f[i]+mod)%mod;
ntt.getr(lim);
ntt(f,1),ntt(ans,1);
for(int i=0;i<lim;i++)ans[i]=1ll*ans[i]*f[i]%mod,f[i]=0;
ntt(ans,-1);
for(int i=m;i<lim;i++)ans[i]=0;
}
}
int f[maxn],d[maxn],t[maxn],fac[maxn],ifac[maxn],lim=1<<17,tpd[maxn];
int main(){
fac[0]=1;
for(int i=1;i<lim;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[lim-1]=pow(fac[lim-1],mod-2);
for(int i=lim-1;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
for(int i=0;i<lim;i++)f[i]=1ll*pow(2,1ll*i*(i-1)/2%(mod-1))*ifac[i]%mod;
ln(f,d,lim);
for(int i=0;i<lim;i++)d[i]=1ll*d[i]*i%mod;
int testcase=5;
der(d,tpd,lim);
ntt.getr(lim<<1);
ntt(tpd,1);
while(testcase--){
int n;
scanf("%d",&n);
for(int i=0;i<lim;i++)f[i]=0,t[i]=1ll*(mod-n)*d[i]%mod;
exp(t,f,lim);
ntt.getr(lim<<1);
ntt(f,1);
for(int i=0;i<lim<<1;i++)f[i]=1ll*f[i]*tpd[i]%mod;
ntt(f,-1);
printf("%lld\n",1ll*pow(n,mod-2)*f[n-1]%mod*fac[n-1]%mod);
}
return 0;
}