题目描述

　　对于一个\(1\)到\(n\)的排列\(a_1,a_2,a_3,\ldots,a_n\)，我们定义这个排列的\(P\)值和\(Q\)值：

　　对于每个\(a_i\)，如果存在一个最小的\(j\)使得\(i<j\)且\(a_i<a_j\)，那么将\(a_i\)和\(a_j\)连一条无向边。于是就得到一幅图。计算这幅图每个联通块的大小，将它们相乘，得到\(P\)。记\(Q=P^k\)。

　　对于\(1\)到\(n\)的所有排列，我们想知道它们的\(Q\)值之和。由于答案可能很大，请将答案对\(998244353\)取模。

　　\(n,k\leq 100000\)

题解

　　考虑从小到大插入这\(n\)个数。

　　设\(f_i\)为所有\(1\)~\(i\)的排列的\(Q\)值之和。

　　考虑\(i\)的位置，当\(i\)在第\(j\)个位置的时候，前面\(j\)个点是联通的，后面\(i-j\)个点与前面\(j\)个点不连通。

　　时间复杂度：\(O(n\log k+n\log^2n)\)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
            
              pii;typedef pair
             
               pll;void sort(int &a,int &b){ if(a>b) swap(a,b);}void open(const char *s){#ifndef ONLINE_JUDGE char str[100]; sprintf(str,"%s.in",s); freopen(str,"r",stdin); sprintf(str,"%s.out",s); freopen(str,"w",stdout);#endif}const ll p=998244353;ll fp(ll a,ll b){ ll s=1; while(b) { if(b&1) s=s*a%p; a=a*a%p; b>>=1; } return s;}namespace ntt{ const ll g=3; ll w1[270010]; ll w2[270010]; int rev[270010]; int n; void init(int m) { n=1; while(n
              
               >1]>>1)|(i&1?n>>1:0); } void ntt(ll *a,int t) { ll u,v,w,wn; int i,j,k; for(i=0;i
               
                >1); init(2*m); copy_clear(x,a,m); copy_clear(y,b,m>>1); ntt(x,1); ntt(y,1); int i; for(i=0;i
                
                 >1; solve(l,mid); ntt::init(r-l+1); int i; for(i=l;i<=mid;i++) a[i-l]=f[i]*ifac[i]; for(i=l;i<=r;i++) b[i-l]=ex[i-l]; for(i=mid-l+1;i