先对于 \(n=4\) 打表所有的排列，然后观察规律。
考虑经典套路拆逆序对贡献为每一位的分别贡献。（后面比它小的数）
给个贡献的表感受一下（左边排列右边贡献）：
1 2 3 4|0 0 0 0
1 2 4 3|0 0 1 0
1 3 2 4|0 1 0 0
1 3 4 2|0 1 1 0
1 4 2 3|0 2 0 0
1 4 3 2|0 2 1 0
2 1 3 4|1 0 0 0
2 1 4 3|1 0 1 0
然后我们发现对于第 \(i\) 位的贡献的 “循环节” 是一个下限为 \(0\)，上限为 \(n-i\)，公差为 \(1\) 的等差数列但是每个数字会重复 \((n-i)!\) 次。
还有更神奇的事情，当 \(i+1\) 的贡献循环一次时，\(i\) 的贡献加一！
于是考虑将原数组 \(a\) 的逆序对用树状数组/线段树处理后从右向左考虑贡献，记录 \(i+1\) 位的第一次为 \(0\) 的地方，对于最前边和最后面不是 “循环节” 的地方暴力加答案，“循环节” 直接用等差数列求即可。
复杂度上，对于 \((n-i)>20\) 的 \(i\)，贡献最多会改变一次（\(20!>10^{18}\)），因此复杂度为 \(O(n\log n+20^2)\)。
#include<bits/stdc++.h>
#define int __int128
using namespace std;
namespace kong{bool st;}
namespace zhu{
struct{int l,r,sum,lazy;
}tr[2002000];
#define ls (id<<1)
#define rs (id<<1|1)
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sm(x) tr[x].sum
#define lz(x) tr[x].lazy
#define mid ((l(id)+r(id))>>1)
#define up sm(id)=sm(ls)+sm(rs)
#define dw\sm(ls)+=lz(id)*(r(ls)-l(ls)+1);\sm(rs)+=lz(id)*(r(rs)-l(rs)+1);\lz(ls)+=lz(id);\lz(rs)+=lz(id);\lz(id)=0;
void build(int id,int l,int r){l(id)=l,r(id)=r;if(l==r) return;build(ls,l,mid);build(rs,mid+1,r);
}
void add(int id,int l,int r,int y){if(l(id)>=l&&r(id)<=r){sm(id)+=(r(id)-l(id)+1)*y;lz(id)+=y;return;}dw;if(l<=mid){add(ls,l,r,y);}if(r>mid){add(rs,l,r,y);}up;
}
int que(int id,int x){if(l(id)==r(id)){return sm(id);}dw;if(x<=mid){return que(ls,x);}else{return que(rs,x);}
}
#undef sm
int n,a[500500],k,mod,sum[30],st[500500];
int sm(int x){if(x<=20) return sum[x];else return 2e18;
}
string main(){freopen("army.in","r",stdin);freopen("army.out","w",stdout); long long t1,t2,t3;cin>>t1>>t2>>t3;n=t1,k=t2,mod=t3;sum[0]=1;for(int i=1;i<=20;i++){sum[i]=sum[i-1]*i;}for(int i=1;i<=n;i++){cin>>t1;a[i]=t1;}build(1,1,n);for(int i=n;i>=1;i--){st[i]=que(1,a[i]);add(1,a[i]+1,n,1);}int lstbh=1,ans=0;for(int i=n-1;i>=1;i--){if(!lstbh){ans=(ans+k*st[i]%mod)%mod;continue;}int t=k,now=st[i]+1,mx=n-i,j=lstbh,twc=sm(n-i);
// cout<<"---------\n";
// cout<<i<<'\n';
// cout<<st[i]<<' '<<mx<<' '<<lstbh<<'\n';ans=(ans+lstbh*st[i]%mod)%mod;t-=lstbh;
// cout<<"初始 ："<<ans<<" "<<t<<'\n';while(now<=mx&&t>=twc){j+=twc;t-=twc;ans=(ans+twc*now%mod)%mod;now++;}
// cout<<"前端杂碎："<<ans<<" "<<t<<'\n';if(now<=mx){lstbh=0;ans=(ans+t*now%mod)%mod;
// cout<<"死";continue;}lstbh=j;int xhc=sm(n-i+1);ans=(ans+(t/xhc)*twc%mod*((0+mx)*(mx+1)/2%mod)%mod)%mod;t=t%xhc;
// cout<<"循环 ："<<ans<<" "<<t<<'\n';now=0;while(t>=twc){t-=twc;ans=(ans+twc*now%mod)%mod;now++;}ans=(ans+t*now%mod)%mod;
// cout<<"尾端杂碎："<<ans<<" "<<t<<'\n';}long long out=(ans%mod+mod)%mod;cout<<out<<'\n';return "last";
}
}
namespace kong{bool ed;double MB(){return (&st-&ed)/1048576.0;}}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cerr<<zhu::main()<<'\n'<<kong::MB()<<'\n';
}
/*
5 9 1000000007
5 2 4 3 1 */