需要开一个新的分类了，生成函数相关

这道题确实非常的入门

分析得知，不合法方案就是存在一个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
    
     #include
     
      #include
      
       #define N 280010#define M 998244353#define LL long longusing 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
       
        >=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
        
         >1);    int m=1; for(;m
         
          <<=1); for(int i=n;i