一个合法正整数序列，满足：对于每个在序列中出现过的数\(k\)，满足\(k-1\)在最后一个\(k\)前出现过。
对于每个\(k\)，统计在所有序列中\(k\)出现的总次数。
\(n\le 10^5\)
首先有个神仙转化：
记二元组\((val,pos)\)表示值为\(val\)，在\(pos\)位置出现。对其以\(val\)为第一关键字从小到大排序，\(pos\)为第二关键字从大到小排序。如果序列合法，那么相邻两个\(val\)不相同的，前者的\(pos\)小于后者。
发现每个排列对应着一个合法的序列，构造方式：在pos前者小于后者的位置断开，每段表示某个\(val\)的分布。
现在考虑计算\(i\)的答案。枚举\(j\)表示对于第\(j\)位，排列\([1,j]\)分成了\(i\)段（即有\(j-i\)处下降）。于是答案为\(\sum_{j=i}^nE(j,j-i)\binom{n}{j}(n-j)!\)。其中\(E\)为欧拉数。
为了好看一些改写成\(\sum_{j=i}^nE(j,i-1)\binom{n}{j}(n-j)!\)，然后给\(i\)下标平移一位，于是\(ans_i=\sum_{j=i+1}^nE(j,i)\binom{n}{j}(n-j)!\)。为了更好看一些\(j\)的枚举下界改为\(i\)，最后特殊减去\(ans_0\)多余的贡献即可。
然后就是喜闻乐见的推式子环节：
\[ans_i=\sum_{j=i}^n E(j,i)\binom{n}{j}(n-j)!\\ =\sum_{j=i}^n\binom{n}{j}(n-j)!\sum_{k=i}^j\binom{k}{i}(-1)^{k-i}(e^x-1)^{j-k}j![x^j]\\ =n!\sum_{k=i}^n\binom{k}{i}(-1)^{k-i}\sum_{j=k}^n(e^x-1)^{j-k}[x^j]\\ =n!\sum_{k=i}^n\binom{k}{i}(-1)^{k-i}\sum_{j=0}^{n-k}(e^x-1)^{j}[x^{j+k}]\\ =n!\sum_{k=i}^n\binom{k}{i}(-1)^{k-i}\sum_{j=0}^{n-k}(\frac{e^x-1}{x})^{j}[x^{k}]\\ \]对于每个\(k\in[0,n]\)求出右边的东西，然后就可以卷积搞定。
\[令F(x)=\frac{e^x-1}{x},求出g_k=\sum_{i=0}^{n-k}F^i[x^k]\\ \sum_{i=0}^{n-k}F^i=\frac{1}{1-F}-\frac{F^{n-k+1}}{1-F}\\ \frac{1}{1-F}很好算。计算\frac{F^{n-k+1}}{1-F}[x^k]\\ \frac{F^{n-k+1}}{1-F}[x^k]\\ =\frac{(xF)^{n-k+1}}{1-F}[x^{n+1}]\\ =[x^{n+1}y^{n-k+1}]\sum_i\frac{(xyF)^{i}}{1-F}\\ =[x^{n+1}y^{n-k+1}]\frac{1}{1-xyF}\frac{1}{1-F} \]转化成多项式复合的形式：
\[设W(x)=xF(x),构造F(x)=H(W(x))，可得\frac{W(x)}{H(W(x))}=x\\ 设G(x)=\frac{1}{1-xy}\frac{1}{1-H(x)}，则G(W(x))=\frac{1}{1-xyF}\frac{1}{1-F}\\ 现在要求[x^{n+1}]G(W(x)) \]拉格朗日反演。设\(P(x)\)为\(W(x)\)的复合逆。带入\(H\)的定义式得\(\frac{x}{P(x)}=H(x)\)。
\[[x^{n+1}]G(W(x))\\ =\frac{1}{n+1}[x^n]G'(x)(\frac{x}{P(x)})^{n+1}\\ =\frac{1}{n+1}[x^n]G'(x)H(x)^{n+1}\\ =\frac{1}{n+1}[x^n]\left(\frac{y}{(1-xy)^2(1-H(x))}+\frac{H'(x)}{(1-xy)(1-H(x))^2}\right)H(x)^{n+1}\\ 提取y^{k}项系数（k\in[1,n+1]），并且忽略前面的常数：\\ =[x^ny^k]\left(\frac{y}{(1-H(x))}\sum_{i\ge 0}(i+1)(xy)^i+\frac{H'(x)}{(1-H(x))^2}\sum_{i\ge 0}(xy)^i\right)H(x)^{n+1}\\ =[x^n]\left(\frac{kx^{k-1}}{1-H(x)}+\frac{H'(x)x^k}{(1-H(x))^2}\right)H(x)^{n+1}\\ =[x^{n-k+1}]\frac{kH(x)^{n+1}}{1-H(x)}+[x^{n-k}]\frac{H'(x)H(x)^{n+1}}{(1-H(x))^2}\\ =[x^{n-k+2}]\frac{kH(x)^{n+1}}{\frac{1-H(x)}{x}}+[x^{n-k+2}]\frac{H'(x)H(x)^{n+1}}{(\frac{1-H(x)}{x})^2}\\ \]最后问题是求\(H(x)\)。
\[\frac{xF(x)}{H(xF(x))}=\frac{e^x-1}{H(e^x-1)}=x\\ 构造T(e^x-1)=x，可得T(x)=\ln(1+x)\\ 令z=e^x-1，得\frac{z}{H(z)}=T(z)\\ 把z换成x代入，H(x)=\frac{x}{\ln(1+x)} \]using namespace std;
#include <bits/stdc++.h>
#define N (262144+10)
#define ll long long
#define mo 998244353
ll qpow(ll x,ll y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
int n;
int g[N],ans[N];
ll fac[N],ifac[N],inv[N];
void initC(int n){
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%mo;
ifac[n]=qpow(fac[n]);
for (int i=n-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
for (int i=1;i<=n;++i)
inv[i]=ifac[i]*fac[i-1]%mo;
}
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
int re[N],nN;
void setlen(int n){
int bit=0;
for (nN=1;nN<=n;nN<<=1,++bit);
for (int i=1;i<nN;++i)
re[i]=re[i>>1]>>1|(i&1)<<bit-1;
}
void dft(int A[],int flag){
for (int i=0;i<nN;++i)
if (i<re[i])
swap(A[i],A[re[i]]);
static int wnk[N];
for (int i=1;i<nN;i<<=1){
ll wn=qpow(3,flag==1?(mo-1)/(2*i):mo-1-(mo-1)/(2*i));
wnk[0]=1;
for (int k=1;k<i;++k)
wnk[k]=wnk[k-1]*wn%mo;
for (int j=0;j<nN;j+=i<<1)
for (int k=0;k<i;++k){
ll x=A[j+k],y=(ll)A[j+k+i]*wnk[k];
A[j+k]=(x+y)%mo;
A[j+k+i]=(x-y)%mo;
}
}
for (int i=0;i<nN;++i)
A[i]=(A[i]+mo)%mo;
if (flag==-1){
ll invn=qpow(nN);
for (int i=0;i<nN;++i)
A[i]=A[i]*invn%mo;
}
}
void clear(int A[],int siz=nN){memset(A,0,sizeof(int)*siz);}
void multi(int c[],int a[],int b[],int n){
static int A[N],B[N];
setlen(n*2);
clear(A),memcpy(A,a,sizeof(int)*(n+1)),dft(A,1);
if (a==b)
for (int i=0;i<nN;++i) A[i]=(ll)A[i]*A[i]%mo;
else{
clear(B),memcpy(B,b,sizeof(int)*(n+1)),dft(B,1);
for (int i=0;i<nN;++i) A[i]=(ll)A[i]*B[i]%mo;
}
dft(A,-1);
for (int i=0;i<=n*2;++i) c[i]=A[i];
}
void getinv(int c[],int a[],int n){
static int b[N],A[N],B[N];
int nn=1;
for (;nn<n;nn<<=1);
clear(b,nn);
// assert(a[0]);
b[0]=qpow(a[0]);
for (int i=1;i<n;i<<=1){
setlen(i*3-1);
clear(A),clear(B);
memcpy(A,a,sizeof(int)*min(n,i*2));
memcpy(B,b,sizeof(int)*i);
dft(A,1),dft(B,1);
for (int j=0;j<nN;++j) B[j]=(ll)B[j]*B[j]%mo*A[j]%mo;
dft(B,-1);
for (int j=0;j<i*2;++j) b[j]=(2ll*b[j]-B[j]+mo)%mo;
}
memcpy(c,b,sizeof(int)*n);
}
void getln(int c[],int a[],int n){
static int b[N],d[N];
for (int i=1;i<n;++i) b[i-1]=(ll)a[i]*i%mo;
getinv(d,a,n);
multi(b,b,d,n-1);
c[0]=0;
for (int i=0;i<n-1;++i)
c[i+1]=b[i]*inv[i+1]%mo;
}
void getexp(int c[],int a[],int n){
static int b[N],d[N];
int nn=1;
for (;nn<n;nn<<=1);
clear(b,nn);
b[0]=1;
for (int i=1;i<n;i<<=1){
getln(d,b,i*2);
for (int j=0;j<i*2;++j)
d[j]=(a[j]-d[j]+mo)%mo;
d[0]=(d[0]+1)%mo;
multi(d,b,d,i*2-1);
memcpy(b,d,sizeof(int)*(i*2));
}
memcpy(c,b,sizeof(int)*n);
}
void getpow(int c[],int a[],int n,int idx){
static int b[N];
// assert(a[0]);
getln(b,a,n);
for (int i=0;i<n;++i)
b[i]=(ll)b[i]*idx%mo;
getexp(c,b,n);
}
void work0(){
static int a[N];
for (int i=2;i<=n+3;++i)
a[i-2]=(mo-ifac[i])%mo;
getinv(a,a,n+2);
for (int k=0;k<=n;++k)
g[k]=(g[k]+a[k+1])%mo;
}
void work1(){
static int H[N],P[N],a[N],b[N];
for (int i=1;i<=n+3;++i)
H[i-1]=(-(i&1?-1:1)*inv[i]+mo)%mo;
getinv(H,H,n+3);
getpow(P,H,n+2,n+1);
for (int i=1;i<=n+2;++i)
a[i-1]=(mo-H[i])%mo;
getinv(a,a,n+2);
multi(b,P,a,n+2-1);
for (int k=0;k<=n;++k){
int k_=n-k+1;
g[k]=((g[k]-(ll)k_*b[n-k_+2]%mo*inv[n+1])%mo+mo)%mo;
}
multi(a,a,a,n+2-1);
for (int i=1;i<=n+2;++i)
b[i-1]=(ll)H[i]*i%mo;
multi(b,b,P,n+2-1);
multi(b,b,a,n+2-1);
for (int k=0;k<=n;++k){
int k_=n-k+1;
g[k]=((g[k]-(ll)b[n-k_+2]*inv[n+1])%mo+mo)%mo;
}
}
void work2(){
static int a[N],b[N],c[N];
for (int k=0;k<=n;++k) a[k]=fac[k]*g[k]%mo;
for (int k=0;k<=n;++k) b[n-k]=((k&1?-1:1)*ifac[k]+mo)%mo;
multi(c,a,b,n);
for (int i=0;i<n;++i)
ans[i]=c[n+i]*fac[n]%mo*ifac[i]%mo;
}
int main(){
scanf("%d",&n);
initC(n+5);
work0();
work1();
work2();
ans[0]=(ans[0]-fac[n]+mo)%mo;
for (int i=0;i<n;++i)
printf("%d ",ans[i]);
return 0;
}