传送门

有生之年系列节目之「成爷主动找我说话」

给顶点标号,因为循环同构算同一条,强制起点都是$1$。则哈密顿回路的序列就是第一个点为$1$的排列。有$n$条边已经构成回路了,剩下的边随便连。所以$n$个点的哈密顿回路总数为$(n-1)!2^{\frac{n(n-1)}{2}-n}$。

那么我们只要求出有多少个存在哈密顿回路的竞赛图,用总数除一下即可。

下面证明一个结论:「竞赛图是强联通的」与「竞赛图存在哈密顿回路」是等价的。

看着挺对的。不会证,告辞,自行百度吧。

于是问题转化为强联通竞赛图计数。

设$g(n)$为$n$个点的竞赛图数量,$f(n)$为$n$个点的强联通竞赛图数量。显然$g(n)=2^{\frac{n(n-1)}{2}}$。

考虑把$g(n)$分类。按$1$号点所在强联通分量大小分不好使了,因为这个强连通分量和其他点之间也会有边,关系不好确定。

按拓扑序最小的强连通分量大小来分,$g(n)=\sum\limits_{i=1}^nC_n^if(i)g(n-i)$。

后面是个带组合数的卷积,拆开组合数就出来$EGF$了:$\dfrac{g(n)}{n!}=\sum\limits_{i=1}^n\dfrac{f(i)}{i!}\dfrac{g(n-i)}{(n-i)!}$

令$F(x)$为$\{f(n)\}$的$EGF$,$G(x)$为$\{g(n)\}$的$EGF$。

$G=\sum\limits_{n=0}^\infty\dfrac{g(n)}{n!}x^n$

$=\sum\limits_{n=0}^\infty x^n\left([n=0]+\sum\limits_{i=1}^n\dfrac{f(i)}{i!}\dfrac{g(n-i)}{(n-i)!}\right)$

$=1+F\times G$

$F=\dfrac{G-1}{G}$

多项式求逆即可。特判一下$n=2$。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 530005
#define inf 0x3f3f3f3f

const int mod = 998244353;
const int g = 3;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
inline int quickpow(int x,long long y=mod-2){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
    return ans;
}
const int ig = quickpow(g);
int tr[maxn];
inline int qm(int x){return x>=mod?x-mod:x;}
void NTT(int *f,int n,bool t){
    for(register int i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
    for(register int p=2;p<=n;p<<=1){
        int len=p>>1,o=quickpow(t?ig:g,(mod-1)/p);
        for(register int i=0;i<n;i+=p){
            int gen=1,cop;
            for(register int j=i;j<i+len;++j){
                cop=1ll*f[j+len]*gen%mod,gen=1ll*gen*o%mod;
                f[j+len]=qm(f[j]+mod-cop),f[j]=qm(f[j]+cop);
            }
        }
    }
    if(t){
        int inv=quickpow(n);
        for(register int i=0;i<n;++i)f[i]=1ll*f[i]*inv%mod;
    }
}
int A[maxn],B[maxn];
void mul(int *a,int *b,int *c,int n,int lim){
    for(register int i=0;i<n;++i)A[i]=a[i],B[i]=b[i];
    int m=n<<1;
    n=1;
    while(n<m)n<<=1;
    for(register int i=0;i<n;++i)tr[i]=(tr[i>>1]>>1)|(i&1?n>>1:0);
    NTT(A,n,0),NTT(B,n,0);
    for(register int i=0;i<n;++i)A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,n,1);
    for(register int i=0;i<lim;++i)c[i]=A[i];
    for(register int i=0;i<n;++i)A[i]=B[i]=0;
}
int invR[maxn],_invR[maxn];
void Inv(int *f,int *g,int n){
#define R invR
#define _R _invR
    int lim=2;
    R[0]=quickpow(f[0]);
    while(lim<n<<1){
        for(register int i=0;i<lim;++i)_R[i]=R[i],R[i]=f[i];
        for(register int i=1;i<lim<<1;++i)tr[i]=(tr[i>>1]>>1)|(i&1?lim:0);
        NTT(_R,lim<<1,0),NTT(R,lim<<1,0);
        for(register int i=0;i<lim<<1;++i)R[i]=1ll*qm(2+mod-1ll*R[i]*_R[i]%mod)*_R[i]%mod;
        NTT(R,lim<<1,1),lim<<=1;
        for(register int i=lim>>1;i<lim;++i)R[i]=_R[i]=0;
    }
    for(register int i=0;i<n;++i)g[i]=R[i];
    for(register int i=0;i<lim;++i)R[i]=_R[i]=0;
#undef R
#undef _R
}
int G[maxn],_G[maxn],fac[maxn]={1},inv[maxn];
int main(){
    int n=read();
    for(register int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=quickpow(fac[n]);
    for(register int i=n-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    _G[0]=1;
    for(register int i=1;i<=n;++i){
        int c=quickpow(2,(1ll*i*(i-1)>>1)%(mod-1));
        G[i]=_G[i]=1ll*c*inv[i]%mod;
    }
    Inv(_G,_G,n+1),mul(_G,G,G,n+1,n+1),puts("1\n-1");
    for(register int i=3;i<=n;++i)printf("%d\n",1ll*fac[i-1]*quickpow(2,(1ll*i*(i-1)>>1)-i)%mod*quickpow(1ll*G[i]*fac[i]%mod)%mod);
}