题意

某个1~n的排列如果满足：
在1~n-1 这些位置后面将序列断开，使得总可以从右边找到一个数，并且该数不大于左边的所有数，则称该序列为“美妙的”。
给出n，求长度为n的“美妙的序列”的数量。

题解

仔细分析一波，一个序列是不合法的
当且仅当存在某一位$i$，使得$[1,i]$这些位的数字刚好是$[1,i]$的排列
然后我们就可以考虑容斥了
容易得到一个DP方程
$f[n]=n!-\sum{f[i]*(n-i)!}$
容易发现这个是一个卷积的形式

这个东西的话有两个方法处理
1.分治FFT
2.多项式求逆

分治NTT就直接做就可以了
时间复杂度是$nlog^2n$的，不是特别优秀
用递归版的NTT会T

多项式求逆的话
我们定义F就是答案的多项式，f是每一项是阶乘的一个多项式
可以得到
$F=f-F*f$
然后可以得到
$F=\frac{f}{1+f}$
并且一个要注意的地方是，f这个函数在这题里面，第0项是0，但是求逆的时候，是1
然后这个做法就是$nlogn$的了

感觉多项式求逆还是很神奇啊

分治NTT

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL N=400005;
const LL MOD=998244353,g=3;
LL JC[N];
LL f[N];//只有前i个是乱的有多少种方案
LL inv[N];
LL pow (LL x,LL y)
{if (y==1) return x;LL lalal=pow(x,y>>1);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
LL bin[N];
void ntt(LL *a,LL n,LL op)
{for(LL i=0;i<n;i++) bin[i]=(bin[i>>1]>>1)|((i&1)*(n>>1));for(LL i=0;i<n;i++) if(i<bin[i]) swap(a[i],a[bin[i]]);for(LL i=1;i<n;i<<=1){LL wn=pow((LL)g,op==1?(MOD-1)/(2*i):MOD-1-(MOD-1)/(2*i)),w,t;for(LL j=0;j<n;j+=i<<1){w=1;for(LL k=0;k<i;k++){t=w*a[i+j+k]%MOD;w=w*wn%MOD;a[i+j+k]=(a[j+k]-t+MOD)%MOD;a[j+k]=(a[j+k]+t)%MOD;}}}
}
LL a[N],b[N];
void solve (int l,int r)
{if (l==r) return ;int mid=(l+r)>>1;solve(l,mid);int tot=0,lalal=r-l;for (int u=l;u<=mid;u++)    a[tot++]=f[u];for (int u=0;u<=lalal;u++)   b[u]=JC[u];LL h=1;while (h<=lalal) h<<=1;h<<=1;for (int u=tot;u<h;u++) a[u]=0;for (int u=lalal+1;u<h;u++) b[u]=0;ntt(a,h,1);ntt(b,h,1);for (int u=0;u<h;u++) a[u]=a[u]*b[u]%MOD;ntt(a,h,-1);for (int u=0;u<h;u++) a[u]=a[u]*inv[h]%MOD;int tot1=mid-l+1;for (int u=tot1;u<=r-l;u++) f[u-tot1+1+mid]=((f[u-tot1+1+mid]-a[u])%MOD+MOD)%MOD;solve(mid+1,r);
}
int read()
{int x=0;char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x;
}
int main()
{   JC[1]=1;for (LL u=2;u<=400000;u++) JC[u]=JC[u-1]*u%MOD;for (int u=1;u<=400000;u++) f[u]=JC[u];inv[1]=1;for (int u=2;u<=400000;u++) inv[u]=(MOD-MOD/u)*inv[MOD%u]%MOD;solve(1,100000);LL T;T=read();while (T--) printf("%I64d\n",f[read()]);return 0;
}

多项式求逆

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL N=400005;
const LL MOD=998244353,g=3,gi=332748118;
LL read()
{LL x=0;char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x;
}
LL JC[N];
LL f[N];//只有前i个是乱的有多少种方案
LL inv[N];
LL pow (LL x,LL y)
{if (y==1) return x;LL lalal=pow(x,y>>1);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
LL bin[N];
void ntt(LL *a,LL n,LL op)
{for (LL u=0;u<n;u++) bin[u]=(bin[u>>1]>>1)|((u&1)*(n>>1));for (LL u=0;u<n;u++) if (u<bin[u]) swap(a[u],a[bin[u]]);for (LL u=1;u<n;u<<=1){LL wn=pow(op==1?g:gi,(MOD-1)/(u<<1)),w,t;for (LL i=0;i<n;i=i+(u<<1)){w=1;for (LL j=0;j<u;j++){t=w*a[u+i+j]%MOD;a[u+i+j]=(a[i+j]-t+MOD)%MOD;a[i+j]=(a[i+j]+t)%MOD;w=w*wn%MOD;}}}if(op==-1){LL Inv=pow(n,MOD-2);for(LL i=0;i<n;i++) a[i]=a[i]*Inv%MOD;}
}
LL tmp[N];
void get_inv (LL deg,LL *a,LL *b)//对a进行多项式求逆 
{if (deg==1){b[0]=pow(a[0],MOD-2);return ;}get_inv((deg+1)>>1,a,b);LL now=1;while (now<deg) now<<=1;now<<=1;copy(a,a+deg,tmp);fill(tmp+deg,tmp+now,0);ntt(tmp,now,1LL);ntt(b,now,1LL);for (LL u=0;u<now;u++){b[u]=(2-b[u]*tmp[u]%MOD)*b[u]%MOD;if (b[u]<0) b[u]+=MOD;}ntt(b,now,-1);fill(b+deg,b+N,0);
}
LL b[N];
int main()
{LL n=100000;JC[0]=1;for (LL u=1;u<=n;u++) JC[u]=JC[u-1]*u%MOD;for (LL u=1;u<=n;u++) f[u]=JC[u];get_inv(n+1,JC,b);LL now=1;while (now<(n+1)) now<<=1;now<<=1;ntt(f,now,1);ntt(b,now,1);for (LL u=0;u<now;u++) f[u]=f[u]*b[u]%MOD;ntt(f,now,-1);LL T;T=read();while (T--) printf("%I64d\n",f[read()]);return 0;
}