需要开一个新的分类了，生成函数相关
这道题确实非常的入门
分析得知，不合法方案就是存在一个i<n使得s[1..i]是一个1..i的排列
那么设f[n]表示n的答案，可以得到f[n]=n!-∑f[i]*(n-i)! (i<n)
移项得到∑f[i]*(n-i)!=n! (i<=n)
发现可以生成函数
设F(x)=∑f[i]*x^i, G(x)=∑i!*x^i (i=1..∞)
根据上面那条式子得到F(x)*G(x)=G(x)-1
得到F(x)=1-1/G(x) 求逆就好了
当然如果不用生成函数，也可以直接用上面的式子做分治FFT，复杂度会多一个log
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 280010
#define M 998244353
#define LL long long
using namespace std;
int W[N],iW[N];
inline LL pow(LL x,LL k,LL s=1){
for(;k;x=x*x%M,k>>=1) k&1?s=s*x%M:0;
return s;
}
inline void init(){
for(int j=1;j<=N;j<<=1){
W[j]=pow(3,(M-1)/j);
iW[j]=pow(W[j],M-2);
}
}
inline void NTT(int* A,int n,int g){
static int b[N];
for(int i=0,j,k,t;i<n;++i){
for(j=0,k=i,t=n-1;t;t>>=1,k>>=1)
j=(j<<1)|(k&1);
b[j]=A[i];
}
for(int m=2;m<=n;m<<=1){
LL w=g?W[m]:iW[m],u,v,z;
for(int i,k=m>>1,j=0;j<n;j+=m)
for(z=1,i=0;i<k;++i,z=z*w%M){
u=b[i+j]; v=z*b[i+j+k]%M;
b[i+j]=(u+v)%M; b[i+j+k]=(u-v+M)%M;
}
}
if(!g){
g=pow(n,M-2);
for(int i=0;i<n;++i) A[i]=(LL)b[i]*g%M;
} else memcpy(A,b,n<<2);
}
struct poly{
int n,a[N];
inline int len(){ return n; }
inline int& operator[] (int i){ return a[i]; }
inline void trans(int* b,int m){
n=m; memcpy(a,b,m+1<<2);
}
};
inline poly operator+ (poly a,poly b){
poly c; c.n=max(a.n,b.n);
for(int i=0;i<=c.n;++i)
c[i]=(a[i]+b[i])%M;
return c;
}
inline poly operator- (poly a,poly b){
poly c; c.n=max(a.n,b.n);
for(int i=0;i<=c.n;++i)
c[i]=(a[i]-b[i]+M)%M;
return c;
}
inline poly operator* (poly a,poly b){
poly c; c.n=a.n+b.n;
if((LL)a.n*b.n<=-1){
for(int i=0;i<=a.n;++i)
for(int j=0;j<=b.n;++j)
c[i+j]=(c[i+j]+(LL)a[i]*b[j])%M;
return c;
}
int n=1; for(;n<=c.n;n<<=1);
static int A[N],B[N];
memset(A,0,n<<2);
memset(B,0,n<<2);
memcpy(A,a.a,a.n+1<<2);
memcpy(B,b.a,b.n+1<<2);
NTT(A,n,1); NTT(B,n,1);
for(int i=0;i<n;++i) A[i]=(LL)A[i]*B[i]%M;
NTT(A,n,0);
c.trans(A,c.n); return c;
}
int v[N],iA[N],iB[N];
inline void gInv(int n){
if(n==1){ *iA=pow(*v,M-2); return; }
gInv(n+1>>1);
int m=1; for(;m<n+n+3;m<<=1);
for(int i=n;i<m;++i) iA[i]=iB[i]=0;
memcpy(iB,v,n<<2);
NTT(iA,m,1); NTT(iB,m,1);
for(int i=0;i<m;++i)
iA[i]=iA[i]*(M+2-((LL)iA[i]*iB[i]%M))%M;
NTT(iA,m,0);
for(int i=n;i<m;++i) iA[i]=0;
}
inline poly operator~ (poly x){
poly y; y.n=x.n;
for(int i=0;i<=x.n;++i) v[i]=x[i];
gInv(x.n+1);
y.trans(iA,x.n);
return y;
}
inline void div(poly a,poly b,poly& d,poly& r){
int n=a.n,m=b.n;
if(n<m){ d.n=d[0]=0; r=a; return; }
int len=1; for(;len<n+n;len<<=1);
poly ra=a,rb=b;
reverse(ra.a,ra.a+n+1);
reverse(rb.a,rb.a+m+1);
for(int i=n-m+1;i<=rb.n;++i) rb[i]=0;
rb.n=n-m; rb=~rb;
d=ra*rb; d.n=n-m; reverse(d.a,d.a+d.n+1);
r=a-(b*d); for(r.n=m;!r[r.n];r.n--);
}
inline poly operator/ (poly a,poly b){poly d,r; div(a,b,d,r); return d;}
inline poly operator% (poly a,poly b){poly d,r; div(a,b,d,r); return r;}
inline void input(poly& a){
int n,s[10000];
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",s+i);
a.trans(s,n-1);
}
inline void output(poly a){
for(int i=0;i<=a.n;++i)
printf("%d ",a[i]);
puts("");
}
poly a;
int main(){
init(); int m=120010; a[0]=1; a.n=m-1;
for(int i=1;i<m;++i) a[i]=(LL)a[i-1]*i%M;
a=~a;
for(int i=0;i<m;++i) a[i]=(M-a[i])%M;
++a[0]; int T; scanf("%d",&T);
for(int x;T--;printf("%d
",a[x])) scanf("%d",&x);
}