大概进行了一个题解的整理。以及对于各位大佬题解没细讲的东西的补充。

多重集的康托展开。我们类似于平常的康托展开。假设枚举到第 $i$ 位，在 $i$ 即 $i$ 右边元素 $x$ 出现了 $c_x$ 次。容易想到把一个小于 $a_i$ 的数放在 $i$ 的位置。考虑造成的康托值的贡献为 $T$ 我们容易知道将 $i$ 到 $n$ 这 $n-i+1$ 个元素构成的不同排列为 $\frac{(n-i+1)!}{\prod c_i!}$ 而令 $S = \sum_{x<a_i} c_x$ 则容易得到 $T = \frac{S \cdot (n-i)!}{\prod c_i!}$ 我们发现从后往前更容易计算。对于 $S$ 我们使用树状数组即可。

如何解决模数 $m$ 不一定是质数的情况。考虑把 $m$ 质因数分解成 $p_1^{b_1} \cdot p_2^{b_2} … p_k^{b_k}$ 然后从后往前计算 $\frac{S \cdot (n-i)!}{\prod c_i!}$ 时用 $p$ 去分解每个乘或除以的数。如果还剩下 $x$ 那么若是乘直接记录 $x$ 否则与 $m$ 一定互质，则运用欧拉定理 $x^{\phi(m)} \equiv 1 \pmod m$ 即可得到 $x$ 在模 $m$ 意义下的逆元为 $x^{\phi(m)-1}$ 故解决。

不懂之处可以看代码。

#include <bits/stdc++.h>

using namespace std;

const long long N = 3e5 + 5, K = 3e5;

long long inv[N], mod, n, m, a[N], tr[N], c[N], phim, p[N], b[N], ans[N], sum = 1, tot;

long long D(long long x, long long y) {
  long long sum = 1;
  for (; y; y /= 2, x = (x * x % mod)) {
    if (y & 1) {
      sum = (sum * x % mod);
    }
  }
  return sum % mod;
}

long long lowbit(long long x) {
  return (x & (-x));
}

long long Ans(long long x) {
  long long ans = 0;
  x--;
  for (long long i = x; i; i -= lowbit(i)) {
    ans += tr[i];
  }
  return ans;
}

void add(long long x, long long o) {
  for (long long i = x; i <= K; i += lowbit(i)) {
    tr[i] += o;
  }
}

void Jia(long long x) {
  for (long long i = 1; i <= tot; i++) {
    for (; x % p[i] == 0; x /= p[i]) {
      ans[i]++;
    }
  }
  sum *= x;
  sum %= mod;
}

void Jian(long long x) {
  for (long long i = 1; i <= tot; i++) {
    for (; x % p[i] == 0; x /= p[i]) {
      ans[i]--;
    }
  }
  sum *= inv[x];
  sum %= mod;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> mod;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
  }
  long long x = mod, phim = mod;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      phim /= i;
      phim *= (i - 1);
      p[++tot] = i;
      for (; x % i == 0; x /= i) {
        b[tot]++;
      }
    }
  }
  if (x != 1) {
    phim /= x;
    phim *= (x - 1);
    p[++tot] = x;
    b[tot] = 1;
  }
  for (long long i = 1; i <= n; i++) {
    inv[i] = D(i, phim - 1);
  }
  add(a[n], 1);
  c[a[n]]++;
  long long ss = 1;
  for (long long i = n - 1; i; i--) {
    long long x = Ans(a[i]);
    add(a[i], 1);
    c[a[i]]++;
    Jia(n - i), Jian(c[a[i]]);
    if (x == 0) {
      continue;
    }
    Jia(x);
    long long cnt = sum;
    for (long long j = 1; j <= tot; j++) {
      cnt *= D(p[j], ans[j]);
      cnt %= mod;
    }
    cnt %= mod;
    ss += cnt;
    ss %= mod;
    Jian(x);
  }
  cout << ss;
  return 0;
}