这道题如果不是任意模数的话还是比较平凡的（
这道题的式子其实很好推，根据康托展开的思路，一位一位考虑，只不过是多重集，可能有重复情况，排除即可，每一位的式子为：
\[ans_i=\dfrac{(n-i)!}{\prod cnt_j}\times\sum^n_{k=i+1}[ a_k<a_i] \]（\(cnt_j\) 为 \(i-n\) 之间 \(j\) 的个数，\(a_i\) 为第 \(i\) 位的值）
后面的和式为 \(i-n\) 之间值大于第 \(i\) 位的值的数量，同康托展开，用树状数组处理，接下来考虑如何处理任意模数。
\(cnt_j\) 中有可能会出现与 \(p\) 不互质的情况，这种条件下不存在逆元，所以可以借鉴扩展卢卡斯的思路，把分子和分母中 \(p\) 的质因子拆分出来，再来计算分母逆元，最后累计答案的时候再把 \(p\) 分离出来的质因子乘进去即可。
另外，对于每一位的答案肯定不能单独计算，否则时间复杂度会爆掉，所以考虑答案递推，首先从后向前推肯定相对简单，考虑每往前走一步对答案的影响，假设从 \(t+1\) 走到 \(t\) 分子，分子从 \((n-t-1)!\) 变为 \((n-t)!\) 乘上了 \(n-t\)，\(cnt_{a_t}\) 增加了1，相当于乘上了 \(\dfrac{cnt_{a_t}-1}{cnt_{a_t}}\)，把上面两式分离质因子求逆元乘进答案递推即可，初始状态 \(ans_n=0\)
Code：
#include<bits/stdc++.h>
#define N 300005ll
#define int long long
using namespace std;
int n,m,s[N],ans=1,buk[N],cnt[100];
int x,y,fac[100][N],base[100],tot;
struct Fenwick{
int c[N];
inline int lowbit(int X) {return X&(-X);}
inline void update(int pos,int val){
for(int i=pos;i<=N-5;i+=lowbit(i))
c[i]+=val;
}
inline int sum(int pos){
int temp=0;
for(int i=pos;i;i-=lowbit(i))
temp+=c[i];
return temp;
}
}T;
void exgcd(int a,int b);
int inv(int a,int p);
void factor(int a);
void change(int &a,int type);
int prod();
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%lld",s+i);
factor(m);
buk[s[n]]++;T.update(s[n],1);
int tmpans=1,tmp;
for(int i=n-1;i>=1;i--){
T.update(s[i],1);
change(tmp,1);
tmpans=tmpans*tmp%m;
tmp=++buk[s[i]];
change(tmp,-1);
tmpans=tmpans*inv(tmp,m)%m;
ans=(ans+tmpans*T.sum(s[i]-1)%m*prod()%m)%m;
}
cout<<ans;
}
void exgcd(int a,int b){
if(!b){
x=1,y=0;
return;
}
exgcd(b,a%b);
int tmp=x;
x=y,y=tmp-a/b*y;
}
int inv(int a,int p){
exgcd(a,p);
return (x%p+p)%p;
}
void factor(int a){
for(int i=2;a!=1;i++)
if(!(a%i)){
base[++tot]=i;
fac[tot][0]=1;
while(!(a%i)) a/=i;
for(int j=1;j<=N-5;j++)
fac[tot][j]=fac[tot][j-1]*i%m;
}
}
void change(int &a,int type){
for(int i=1;i<=tot;i++)
while(!(a%base[i])){
a/=base[i];
cnt[i]+=type;
}
}
int prod(){
int Tmp=1;
for(int i=1;i<=tot;i++)
Tmp=Tmp*fac[i][cnt[i]]%m;
return Tmp;
}