注意到总共有(frac{n!}{n})条本质不同的哈密顿回路，每一条哈密顿回路恰好会出现在(2^{inom{n}{2} - n})个图中，所以我们实际上要算的是强连通有向竞赛图的数量。
设(f_i)表示点数为(i)的强连通竞赛图数，转移考虑用总数(2^inom{i}{2})减去不强连通的图数量。如果竞赛图不强连通，我们可以枚举拓扑序最靠后的一个强连通子图，如果它的大小为(j)，那么剩下(i-j)个点之间的边可以任意连，但是这(i-j)个和这(j)个点之间的边的方向是确定的，可以得到转移(f_i = 2^inom{i}{2} - sumlimits_{j=1}^{i-1} inom{i}{j} 2^inom{i-j}{2} f_j)，直接做复杂度(O(n^2))
然后考虑优化。把(inom{i}{j})拆开然后左右两边各除以(i!)得到(frac{f_i}{i!} = frac{2^inom{i}{2}}{i!} - sumlimits_{j=1}^{i-1} frac{f_j}{j!} frac{2^inom{i-j}{2}}{i-j!})。设多项式(F = sumlimits_{i=1}^n frac{f_i}{i!}x^i)，(G = sumlimits_{i=1}^n frac{2^inom{i}{2}}{i!} x^i)，可以得到(F = G - F * G)，即(F = frac{G}{G + 1})，多项式求逆即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<cassert>
//This code is written by Itst
using namespace std;
#define int long long
const int MOD = 998244353 , _ = (1 << 18) + 3;
int jc[_] , inv[_] , G[_] , H[_] , N;
#define ch2(x) ((x) * ((x) - 1) / 2)
int poww(int a , int b){
int tms = 1;
while(b){
if(b & 1) tms = tms * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return tms;
}
namespace poly{
const int G = 3 , INV = 332748118;
int dir[_] , need , invnd;
void init(int len){
need = 1;
while(need < len) need <<= 1;
invnd = poww(need , MOD - 2);
for(int i = 1 ; i < need ; ++i)
dir[i] = (dir[i >> 1] >> 1) | (i & 1 ? need >> 1 : 0);
}
void NTT(int *arr , int tp){
for(int i = 1 ; i < need ; ++i)
if(i < dir[i])
arr[i] ^= arr[dir[i]] ^= arr[i] ^= arr[dir[i]];
for(int i = 1 ; i < need ; i <<= 1){
int wn = poww(tp == 1 ? G : INV , MOD / i / 2);
for(int j = 0 ; j < need ; j += i << 1){
int w = 1;
for(int k = 0 ; k < i ; ++k , w = w * wn % MOD){
int x = arr[j + k] , y = arr[i + j + k] * w % MOD;
arr[j + k] = x + y >= MOD ? x + y - MOD : x + y;
arr[i + j + k] = x < y ? x + MOD - y : x - y;
}
}
}
if(tp != 1)
for(int i = 0 ; i < need ; ++i)
arr[i] = arr[i] * invnd % MOD;
}
#define clr(x) memset(x , 0 , sizeof(int) * need)
int A[_] , B[_];
void getInv(int *a , int *b , int len){
if(len == 1) return (void)(b[0] = poww(a[0] , MOD - 2));
getInv(a , b , (len + 1) >> 1);
memcpy(A , a , sizeof(int) * len);
memcpy(B , b , sizeof(int) * len);
init(len * 2 + 3); NTT(A , 1); NTT(B , 1);
for(int i = 0 ; i < need ; ++i)
A[i] = A[i] * B[i] % MOD * B[i] % MOD;
NTT(A , -1);
for(int i = 0 ; i < len ; ++i)
b[i] = (2 * b[i] - A[i] + MOD) % MOD;
clr(A); clr(B);
}
}
signed main(){
cin >> N;
jc[0] = 1;
for(int i = 1 ; i <= N ; ++i) jc[i] = jc[i - 1] * i % MOD;
inv[N] = poww(jc[N] , MOD - 2);
for(int i = N - 1 ; i >= 0 ; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
for(int i = 1 ; i <= N ; ++i) G[i] = 1ll * poww(2 , ch2(i)) * inv[i] % MOD;
G[0] = 1; poly::getInv(G , H , N + 1); G[0] = 0;
poly::init(2 * N + 2); poly::NTT(G , 1); poly::NTT(H , 1);
for(int i = 0 ; i < poly::need ; ++i)
G[i] = 1ll * G[i] * H[i] % MOD;
poly::NTT(G , -1);
for(int i = 1 ; i <= N ; ++i)
printf("%d
" , i == 1 ? 1 : (i == 2 ? -1 : poww(G[i] , MOD - 2) * inv[i] % MOD * jc[i - 1] % MOD * poww(2 , ch2(i) - i) % MOD));
return 0;
}