Description
如果对于一个 \(1\sim n\) 的排列满足：
在 \(1\sim n-1\) 这些位置之后将序列断开，使得总可以从右边找一个数，使得该数不会比左边所有数都大，则称该序列是“美妙的”。
给出 \(n\) ，求出长度为 \(n\) 的美妙的序列的数量。多组数据。 \(T,n\leq 10^5\)。对 \(998244353\) 取模。
Solution
暴力DP是 \(O(Tn^2)\) 的。我们需要发现题目的隐藏性质。
如果某个排列不是美妙的，那一定存在一个位置 \(k\) ，使得 \(k\) 右边的最小值大于左边的最大值。也就是说，\(k\) 左边是一个 \(1\sim k\) 的排列。
问题就转化成了求有多少长度为 \(n\) 的排列，使得任意一个前缀都不是 \(1\sim k\) 的排列。
考虑 \(DP\) 。设 \(f[i]\) 表示长度为 \(i\) 的美妙的排列个数。有转移：
\[f[n]=n!-\sum_{i=1}^{n-1}i!\cdot f[n-i]\quad f[0]=0
\]
\]
这个转移的含义是用总方案数减去不合法的方案数，也就是减去所有不美妙的排列。于是枚举最靠右不能满足要求的位置，然后把序列划分成两端。前一段是一个 \(1\sim k\) 的排列，后一段一定是一个美妙的序列（不然一定可以找到一个更靠右的不满足题意的位置）。
这时候就可以分治FFT了。但是别着急，一般分治FFT能做的多项式求逆都可以做。再推几步式子：
\[f[n]=n!-\sum_{i=1}^n i!\cdot f[n-i]
\]
\]
移项：
\[\sum_{i=0}^n i!\cdot f[n-i]=n!
\]
\]
由于有 \(f[0]=0\) 的特殊情况所以需要特殊考虑：
\[\text{当n=0时}\quad \sum_{i=0}^n i!\cdot f[n-i]+1=n!
\]
\]
于是令 \(F\) 为 \(f\) 的生成函数，\(G=\sum\limits_{i=0}^\infty i!\cdot x^i\)，于是就有 \(F\times G+1=G\)，移项可以得到：
\[F=1-\frac1{G}
\]
\]
多项式求逆即可。复杂度 \(O(n\log n)\)。
Code
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
#define int long long
const int n=1e5;
const int N=4e5+5;
const int mod=998244353;
int fac[N];
int tmpa[N];
int b[N],c[N];
int lim,rev[N];
int getint(){
int X=0,w=0;char ch=getchar();
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;return X;
}
int ksm(int a,int b=mod-2,int ans=1){
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;b>>=1;
} return ans;
}
void ntt(int *f,int opt){
for(int i=1;i<lim;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
for(int mid=1;mid<lim;mid<<=1){
int tmp=ksm(3,(mod-1)/(mid<<1));
if(opt<0) tmp=ksm(tmp);
for(int R=mid<<1,j=0;j<lim;j+=R){
int w=1;
for(int k=0;k<mid;k++,w=w*tmp%mod){
int x=f[j+k],y=w*f[j+k+mid]%mod;
f[j+k]=(x+y)%mod,f[j+k+mid]=(mod+x-y)%mod;
}
}
} if(opt<0)
for(int in=ksm(lim),i=0;i<lim;i++) f[i]=f[i]*in%mod;
}
void solveinv(int len,int *a,int *b){
if(!len) return b[0]=ksm(a[0]),void();
solveinv(len>>1,a,b);lim=len+len;
for(int i=1;i<lim;i++) rev[i]=(rev[i>>1]>>1)|(i&1?lim>>1:0);
for(int i=0;i<len;i++) tmpa[i]=a[i];
ntt(tmpa,1),ntt(b,1);
for(int i=0;i<lim;i++) b[i]=b[i]*(2ll-tmpa[i]*b[i]%mod+mod)%mod;
ntt(b,-1);
for(int i=len;i<lim;i++) b[i]=0;
for(int i=0;i<lim;i++) tmpa[i]=0;
}
signed main(){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
solveinv(131072,fac,b);
for(int i=1;i<=n;i++) b[i]=mod-b[i];
int T=getint();
while(T--){
int x=getint();
printf("%lld\n",b[x]);
} return 0;
}