题解：AT_abc387_g [ABC387G] Prime Circuit

· · 题解

问题大意

求有 n 个顶点（有标号）的所有简单无向连通图（即无重边无自环的无向连通图）G 中满足以下条件的图的个数，答案模 998244353。

对于 G 中的每个环，该环中的边数都是质数。

环可以重复经过同一顶点，但不能重复经过同一条边。

解法

借鉴了 at 第二篇题解。

首先我们发现如果图 G 中有重复经过同一顶点的环，那么图 G 绝对不合法。

因为这种环绝对是由两个及以上的简单环（即没有重复经过同一顶点）拼起来的。

而如果这个环由两个简单环拼凑起来，由于原图是简单无向图，于是没有长度为 1 和 2 的环，于是两个简单环的环长就为奇质数，加起来就为大于 2 的偶数，就不是指数，所以不合法。

有由两个以上的简单环拼起来的环的图绝对有由两个简单环拼起来的环，于是也不合法。

所以我们知道绝对不会有两个环有点相交。

于是如果我们将原图的环全部缩成点，那么原图就会变成一棵树。

根据扩展卡莱定理，有 n 个点，组成了 a_1,a_2,a_3,\cdots,a_m 的 m 个连通块，再用边连起来而组成一棵树的方案数为 n^{m-2}\prod_{i=1}^{m}a_i。

想看证明可以看这篇博客，主要因为我不会证。

那么再将式子化简一下，就可以得到 \prod_{i=1}^{m}a_in\over n^2。

那么，由于树上节点可以是环缩成的也可以本来就是一个点，于是环长 s 就可以等于 1 或奇质数。

那么答案就是先枚举缩完点树上有 m 个点，每个点的原大小为 s_i,i\in[1,m]，那么对于每一种情况答案为 {1\over n^2} \sum_{i=1}^ms_i\times n\times C(s_i)。

其中

C(x)=\begin{cases} 1&(x=1)\\ {(x-1)!\over 2}&(x>1) \end{cases}

乘上 C(s_i) 是因为环内的点可以排列，但要求旋转后不一致，所以是 (x-1)!，又因为是无向环，所以还要除以 2。

由于 1\over n^2 与 s 无关，所以可以将所有答案求出后再乘上 1\over n^2。

由于点有标号，所以是排列，所以考虑对于 s 的指数生成函数。

\begin{aligned} F(x)&=\sum_{i=1\vee (i\geqslant3\wedge i\in \mathbb{P})}i\times n\times C(i)\times{x^i\over i!}\\ &=nx+\sum_{i\geqslant3\wedge i\in \mathbb{P}}i\times n\times {(i-1)!\over 2}\times{x^i\over i!}\\ &=nx+\sum_{i\geqslant3\wedge i\in \mathbb{P}}{n\over 2}x^i\\ \end{aligned}

对于总答案 G(x)，其指数生成函数为

\begin{aligned} G(x)=\sum_{i=0}{F(x)^i\over i!}=e^{F(x)} \end{aligned}

多项式 \exp 即可。

答案就是生成函数的第 n 项，其系数为 n![x^n]G(x) 。

别忘了最后再乘上 1\over n^2。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
const int p=998244353,y=3,ny=332748118;
int n;
int r[N],a[N],ans[N],f[N],g[N];
int ksm(int a,int b=p-2){
    int ans=1;
    for(;b;b>>=1,a=a*a%p) if(b&1) ans=ans*a%p;
    return ans;
}
void NTT(int *a,int len,int type){
    for(int i=1;i<len;i++) if(i<r[i]) swap(a[i],a[r[i]]);
    for(int mid=1;mid<len;mid<<=1){
        const int wn=ksm((type?y:ny),(p-1)/(mid<<1));
        for(int R=mid<<1,j=0;j<len;j+=R){
            int w(1);
            for(int k=0;k<mid;k++,w=w*wn%p){
                int x=a[j+k],y=a[j+k+mid]*w%p;
                a[j+k]=(x+y)%p;
                a[j+k+mid]=(x+p-y)%p;
            }
        }
    }
    if(type) return;
    int inv=ksm(len);
    for(int i=0;i<len;i++) a[i]=a[i]*inv%p;
}
void inv(int *a,int *b,int len){
    if(len==1) {b[0]=ksm(a[0]);return;}
    inv(a,b,(len+1)>>1);
    int m=len<<1;
    int limit,l;
    for(limit=1,l=0;limit<m;limit<<=1,l++);
    for(int i=1;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for(int i=0;i<len;i++) f[i]=a[i];
    for(int i=len;i<limit;i++) f[i]=0;
    NTT(f,limit,1),NTT(b,limit,1);
    for(int i=0;i<limit;i++) b[i]=b[i]*((2+p-f[i]*b[i]%p)%p)%p;
    NTT(b,limit,0);
    for(int i=len;i<limit;i++) b[i]=0;
}
void mul(int*f,int *g,int l1,int l2){
    int limit,l;
    for(limit=1,l=0;limit<=l1+l2;limit<<=1,l++);
    for(int i=1;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(f,limit,1),NTT(g,limit,1);
    for(int i=0;i<limit;i++) f[i]=f[i]*g[i]%p;
    NTT(f,limit,0);
    for(int i=limit-1;i>=1;i--) f[i]=f[i-1]*ksm(i,p-2)%p;
}
int h[N];
void ln(int *a,int *b,int len){
    for(int i=1;i<len;i++) h[i-1]=a[i]*i%p;
    inv(a,b,len);
    mul(b,h,len,len-1);
    b[0]=0;
}
void expp(int *a,int *b,int len){
    if(len==1) {b[0]=1;return;}
    expp(a,b,(len+1)>>1);
    int m=len<<1,limit,l;
    for(limit=1,l=0;limit<m;limit<<=1,l++);
    for(int i=0;i<limit;i++) g[i]=0;
    ln(b,g,len);
    for(int i=len;i<limit;i++) g[i]=0;
    for(int i=0;i<len;i++) f[i]=a[i];
    for(int i=len;i<limit;i++) f[i]=0;
    for(int i=1;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(f,limit,1),NTT(g,limit,1),NTT(b,limit,1);
    for(int i=0;i<limit;i++) b[i]=((1-g[i]+p)%p+f[i])%p*b[i]%p;
    NTT(b,limit,0);
    for(int i=len;i<limit;i++) b[i]=0;
}
int pr[N],vis[N],cnt;
signed main(){
    cin>>n;
    for(int i=2;i<=3e5;i++){//筛素数
        if(!vis[i]) pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=3e5;j++){
            vis[i*pr[j]]=1;
            if(!(i%pr[j])) break;
        }
    }
    a[1]=n;
    for(int i=2;i<=cnt;i++) a[pr[i]]=n*((p+1)/2)%p;//F(x)函数
    expp(a,ans,n+10);//多项式exp
    int an=ans[n];//得到第n项
    for(int i=1;i<=n;i++) an=an*i%p;
    cout<<an*ksm(n*n%p,p-2)%p;
    return 0;
}