考场被创死了。
套路，枚举值域 \(i\)，统计 \(\le i\) 和 \(>i\) 相邻的贡献。那么原排列对应一个 \(01\) 序列，其中 \(0\) 表示 \(\le i\)，\(1\) 表示 \(>i\)。
然后拆贡献，考虑每个位置 \(j(1\le j<n)\)，\(j,j+1\) 的组合有 \(00,01,10,11\)，我们只关心每次交换后的组合会怎么变。
于是同一个组合的贡献是一样的，我们统计出四种组合各有多少个，然后矩阵快速幂算方案数。
反思：
考场上想了很多，想过 \(01\) 序列，想过 dp 优化。
但是却往 \(P_i>P_{i-1}\) 的方案数这个错误的方向想了很久，想了 1h 左右吧，最后才发现是个假做法。
想 \(01\) 序列时，却因认为“\(01\) 段个数统计”不可做而放弃了这个方向，而想不到每个位置分开贡献就好了。
还是想题不够老练，思路不够清晰，做题和比赛不够有经验。
菜就多练，但是一定要练！
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn=2e5+10, mod=998244353;
ll n,m,a[maxn],b[maxn],cnt0,cnt1,cnt2,ans;
struct mat{
ll dat[3][3];
const mat operator* (const mat t) const{
mat res;
for(ll i=0;i<3;i++)
for(ll j=0;j<3;j++)
res.dat[i][j]=(dat[i][0]*t.dat[0][j]+dat[i][1]*t.dat[1][j]
+dat[i][2]*t.dat[2][j])%mod;
return res;
}
}base, ret;
int main(){
scanf("%lld%lld",&n,&m);
cnt2=n-1;
for(ll i=1;i<=n;i++) scanf("%lld",a+i), b[a[i]]=i; ll tot=(n-1)*n/2%mod;
for(ll i=1;i<n;i++){
ll x=b[i];
if(x>1){
if(a[x-1]<i) --cnt1, ++cnt0;
else --cnt2, ++cnt1;
}
if(x<n){
if(a[x+1]<i) --cnt1, ++cnt0;
else --cnt2, ++cnt1;
}
base.dat[0][1]=2*(n-i)%mod, base.dat[0][0]=(tot+mod-2*(n-i)%mod)%mod;
base.dat[1][0]=i-1, base.dat[1][2]=n-i-1, base.dat[1][1]=(tot-(n-2)+mod)%mod;
base.dat[2][1]=2*i%mod, base.dat[2][2]=(tot+mod-2*i%mod)%mod;
base.dat[2][0]=base.dat[0][2]=0;
ret.dat[0][0]=ret.dat[0][1]=ret.dat[0][2]=
ret.dat[1][0]=ret.dat[1][1]=ret.dat[1][2]=
ret.dat[2][0]=ret.dat[2][1]=ret.dat[2][2]=0;
ret.dat[0][0]=ret.dat[1][1]=ret.dat[2][2]=1;
ll t=m;
while(t){
if(t&1) ret=ret*base;
base=base*base; t>>=1;
}
ll p=(cnt0*ret.dat[0][1]+cnt1*ret.dat[1][1]+cnt2*ret.dat[2][1])%mod;
ans=(ans+p)%mod;
} printf("%lld",ans);
return 0;
}