有生之年系列节目之「成爷主动找我说话」
给顶点标号，因为循环同构算同一条，强制起点都是$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);
}
