康托展开
将 \(1...n\) 的所有排列按照字典序进行排序，某个排列的排名可以通过康托展开的方法求出。
原理
观察排列 \(2,3,1,4\) 和 \(2,3,4,1\)，发现第一个不同的位置是第三位，而且第一个排列的第三位比第二个小，根据字典序的性质，第一个排列的排名在第二个之前。
从这里我们也可以发现判断某个排列排名之前的排列数量的方法。对于 \(2,3,4,1\) 这个排列，我们逐位分析：
- 第一位：\(2\)，我们根据分类加法计数原理对所有排列进行分类：
- 如果一个排列的第一位是 \(1\)，则后面三位可以任意排列，有 \(3!\) 种情况。
- 如果一个排列的第一位是 \(3,4\)，显然后面如何排列都不满足条件。
- 如果一个排列的第一位是 \(2\)，分为下一类。
- 第二位：\(3\)，我们再对第一位是 \(2\) 的排列进行分类：
- 第二位是 \(1\)，后面的两个数可以任意排列，有 \(2!\) 种情况。
- 第二位是 \(4\)，显然后面如何排列都不满足条件。
- 第二位是 \(3\)，分为下一类
- 第三位：\(4\)：我们对前两位是 \(2,3\) 的排列进行分类：
- 第三位是 \(1\) 对答案产生 \(1!\) 的贡献。
- 第三位是 \(4\) 则是排列 \(2,3,4,1\)。
所以，最终的答案就是 \(1*3! + 1*2! + 1*1! = 9\)，有 \(9\) 个排列的字典序比这个排列小，所以这个排列的排名是 \(10\)。
由此可得比某排列的字典序小的排列数量：
\[\sum_{i=1}^{n}(c_{a[i]} \times (n-i)!) \]其中，\(c_{a[i]}=\sum_{j=i}^n [a[j]<a[i]]\)，表示第 \(i\) 个数后面比 \(a[i]\) 小的数，可以用树状数组计算。
代码实现
洛谷 P5367 【模板】康托展开
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 998244353;
int n, a[N];
int jc[N];
int t[N], ca[N];
int ans = 0;
void add(int id) {
for (int i = id;i <= n;i += (i & (-i))) t[i]++;
}
int query(int id) {
int ret = 0;
for (int i = id;i;i -= (i & (-i))) ret += t[i];
return ret;
}
signed main() {
ios::sync_with_stdio(0);
#ifdef DEBUG
clock_t t0 = clock();
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
// Don't stop. Don't hide. Follow the light, and you'll find tomorrow.
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
jc[0] = 1;
for (int i = 1;i <= n;i++) jc[i] = (jc[i - 1] * i) % mod;
for (int i = n;i;i--) {
ca[i] = query(a[i]);
add(a[i]);
}
for (int i = 1;i <= n;i++) {
ans = (ans + ca[i] * jc[n - i]) % mod;
}
cout << ans + 1 << endl;
#ifdef DEBUG
cerr << "Time used:" << clock() - t0 << "ms" << endl;
#endif
return 0;
}