对于$i\ge P_{i}$的位置，由于$P_{i}$此时正面向下，因此操作$i$并不会改变$k$，不妨撤销此类操作
另外，对于满足$P_{j}=i$的操作$j$，若$j<i$则已经操作$,j>i$则也被撤销，因此不影响
综上，仅对$i<P_{i}$建边$(i,P_{i})$，那么$k$即为其中长度为奇数的极长链个数
对于排列$\{P\}$，按照如下方式构造排列$\{Q\}$：
对所有$i$建边$(i,P_{i})$，假设图中有$m$个环且第$i$个环上的点（沿着边）依次构成序列$\{h_{i}\}$
不妨强制$h_{i,1}\le h_{i,j}$且$h_{1,1}>h_{2,1}>...>h_{m,1}$，则$\{Q\}=\sum_{i=1}^{m}\{h_{i}\}$（指拼接）
从排列$\{Q\}$的角度考虑此问题，那么$k$即为其中长度为奇数的极长连续上升子序列个数
另一方面，不难证明排列$\{P\},\{Q\}$一一对应，因此也即统计所有排列的上述信息
进一步的，将排列中的极长连续上升子序列从前往后标记为$AB$，剩下的位置标记为$C$
确定上述标记后，$k$即为其中$C$的个数，同时限制即$A$小于其下一个数且$C$在末尾或大于其下一个数
（注意并不关心偶数长度的序列，因此不需要考虑$BA$和$BC$之间的大小关系）
根据限制，在所有$B$之后断开，断开后每一段序列限制是独立的，且总是形如若干个$C$（允许为0）$+(AB)$
另外，如果没有$AB$显然必然是最后一段，这可以在最后处理（即以下强制存在$AB$）
在此基础上，进行dp计算，令$f_{i}$表示前$i$个位置的答案，转移即$f_{i}=\sum_{j=2}^{i}{i\choose j}(j-1)W^{j-2}f_{i-j}$
结合最后一段$C$，最终答案即$\sum_{i=0}^{n}{n\choose i}W^{i}f_{n-i}$，显然可以$o(n)$计算
关于上述dp式子的计算，可以使用cdq分治+NTT做到$o(n\log^{2}n)$，或使用生成函数进一步优化
具体的，定义$F(x)=\sum_{i\ge 0}\frac{f_{i}}{i!}x^{i}$，代入转移即
$$
\begin{array}{ll}
F(x)
&=\sum_{i\ge 0}\frac{\sum_{j=2}^{i}{i\choose j}(j-1)W^{j-2}f_{i-j}}{i!}x^{i}\\
&=1+\sum_{j\ge 2}\frac{(j-1)W^{j-2}}{j!}\sum_{i\ge j}\frac{f_{i-j}}{(i-j)!}x^{i}\\
&=1+\sum_{j\ge 2}\frac{(j-1)W^{j-2}}{j!}x^{j}F(x)
\end{array}
$$
简单移项，解得$F(x)=\frac{1}{1-\sum_{j\ge 2}\frac{(j-1)W^{j-2}}{j!}x^{j}}$，那么多项式求逆即可
时间复杂度为$o(n\log n)$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 200005
4 #define mod 998244353
5 #define ll long long
6 int n,W,ans,mi[N],inv[N],rev[N<<2];
7 struct Poly{
8 vector<int>a;
9 Poly(){
10 a.clear();
11 }
12 }a;
13 int qpow(int n,int m){
14 int s=n,ans=1;
15 while (m){
16 if (m&1)ans=(ll)ans*s%mod;
17 s=(ll)s*s%mod,m>>=1;
18 }
19 return ans;
20 }
21 void ntt(Poly &a,int n,int p=0){
22 for(int i=0;i<n;i++)
23 if (i<rev[i])swap(a.a[i],a.a[rev[i]]);
24 for(int i=2;i<=n;i<<=1){
25 int s=qpow(3,(mod-1)/i);
26 if (p)s=qpow(s,mod-2);
27 for(int j=0;j<n;j+=i)
28 for(int k=0,ss=1;k<(i>>1);k++,ss=(ll)ss*s%mod){
29 int x=a.a[j+k],y=(ll)a.a[j+k+(i>>1)]*ss%mod;
30 a.a[j+k]=(x+y)%mod,a.a[j+k+(i>>1)]=(x-y+mod)%mod;
31 }
32 }
33 if (p){
34 int s=qpow(n,mod-2);
35 for(int i=0;i<n;i++)a.a[i]=(ll)a.a[i]*s%mod;
36 }
37 }
38 Poly mul(Poly a,Poly b,int n){
39 int m=1;
40 while (m<n)m<<=1;
41 m<<=1,a.a.resize(m),b.a.resize(m);
42 for(int i=n;i<m;i++)a.a[i]=b.a[i]=0;
43 for(int i=0;i<m;i++)rev[i]=(rev[i>>1]>>1)+((i&1)*(m>>1));
44 ntt(a,m),ntt(b,m);
45 for(int i=0;i<m;i++)a.a[i]=(ll)a.a[i]*b.a[i]%mod;
46 ntt(a,m,1),a.a.resize(n);
47 return a;
48 }
49 Poly get_inv(Poly a,int n){
50 Poly ans;
51 if (n==1){
52 ans.a.push_back(qpow(a.a[0],mod-2));
53 return ans;
54 }
55 Poly s=get_inv(a,(n+1>>1));
56 ans=mul(s,a,n);
57 for(int i=0;i<n;i++)ans.a[i]=(mod-ans.a[i])%mod;
58 ans.a[0]=(ans.a[0]+2)%mod;
59 return mul(ans,s,n);
60 }
61 int main(){
62 scanf("%d%d",&n,&W);
63 mi[0]=inv[0]=inv[1]=1;
64 for(int i=1;i<N;i++)mi[i]=(ll)mi[i-1]*W%mod;
65 for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
66 for(int i=1;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
67 for(int i=0;i<=n;i++){
68 if (!i)a.a.push_back(1);
69 if (i==1)a.a.push_back(0);
70 if (i>=2){
71 int s=(ll)(i-1)*mi[i-2]%mod*inv[i]%mod;
72 a.a.push_back((mod-s)%mod);
73 }
74 }
75 a=get_inv(a,n+1);
76 for(int i=0;i<=n;i++)ans=(ans+(ll)inv[i]*mi[i]%mod*a.a[n-i])%mod;
77 for(int i=1;i<=n;i++)ans=(ll)ans*i%mod;
78 printf("%d\n",ans);
79 return 0;
80 }
View Code