Description：

求所有 $n$ 个点带标号强连通竞赛图中哈密顿回路数量的平均值。

$1\leqslant n\leqslant 10^5$

Solution：

首先 $n$ 个点的哈密顿回路总数为 $\frac{n!}n2^{\binom n2-n}$ ，原因是哈密顿回路有 $\frac{n!}n$ 个，要求这些边都出现，其他边随便连，也就是一个哈密顿回路会出现在 $2^{\binom n2-n}$ 个竞赛图中，那么我们只要统计 $n$ 个点的强连通竞赛图的个数就行了。设 $f[i]$ 表示 $i$ 个点的强连通竞赛图的个数，我们可以枚举拓扑序最小的强连通竞赛图的大小： $$ f[i]=2^{\binom i2}-\sum_{j=1}^{i-1}f[j]\times \binom ij\times 2^{\binom{i-j}2} $$ 拆开就是： $$ f[i]=2^{\binom i2}-i!\sum_{j=1}^{i-1}\frac{f[j]}{j!}\times \frac{2^{\binom{i-j}2}}{(i-j)!} $$ 设 $v[i]=\frac{2^{\binom i2}}{i!}$ ，那么： $$ \frac{f[i]}{i!}=v[i]-\sum_{j=0}^{i-1}\frac{f[j]}{j!}v[i-j] $$ 于是分治 $FFT$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 400010

int ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

#define P 998244353

int fac[MAXN],inv[MAXN];

int v[MAXN];

int cnt[MAXN];

int f[MAXN];

int power(int a,long long b)

{

	int res = 1;

	for(;b > 0;a = 1ll * a * a % P,b = b >> 1)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int inver(int a){return power(a,P - 2);}

int init(int n)

{

	int l = 0,len = 1;

	for(;len <= n;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	return len;

}

void NTT(int f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		int wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			int w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		int ni = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = 1ll * ni * f[i] % P;

	}

	return;

}

int tmp1[MAXN],tmp2[MAXN],res_[MAXN];

void solve(int l,int r)

{

	if(l == r){f[l] = (v[l] - f[l] + P) % P;return;}

	int mid = ((l + r) >> 1);

	solve(l,mid);

	int d2 = r - l,d1 = mid - l;

	for(int i = 0;i <= d1;++i)tmp1[i] = f[i + l];

	for(int i = 0;i <= d2;++i)tmp2[i] = v[i];

	int len = init(d1 + d2);

	NTT(tmp1,len,1);NTT(tmp2,len,1);

	for(int i = 0;i < len;++i)res_[i] = 1ll * tmp1[i] * tmp2[i] % P;

	NTT(res_,len,-1);

	for(int i = 0;i < len;++i)tmp1[i] = tmp2[i] = 0;

	for(int i = mid + 1;i <= r;++i)f[i] = (f[i] + res_[i - l]) % P;

	solve(mid + 1,r);

	return;

}

int main()

{

	scanf("%d",&n);

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = 1ll * i * fac[i - 1] % P;

	inv[n] = power(fac[n],P - 2);

	for(int i = n - 1;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % P;

	for(int i = 0;i <= n;++i)v[i] = 1ll * power(2,1ll * i * (i - 1) / 2 % (P - 1)) * power(fac[i],P - 2) % P; 

	solve(1,n);

	for(int i = 1;i <= n;++i)cnt[i] = 1ll * fac[i - 1] * power(2,max(1ll * i * (i - 1) / 2 - i,0ll)) % P;

	for(int i = 1;i <= n;++i)

	{

		int ans = 1ll * inver(1ll * f[i] * fac[i] % P) * cnt[i] % P;

		if(ans == 0)puts("-1");

		else printf("%d\n",ans);

	}

	return 0;

}