杂项之 - 康托展开

在洛谷上闲逛时无意中看到了这个东东，顺便学了一下

Part1 康托展开是什么

康拓展开是一种将排列映射为一个自然数的双射

康托展开可以用来求一个 \(1\sim n\) 的任意排列的排名。

Part2 康托展开的公式

对于一个排列 \(a_1 \dots a_n\)
把 \(1\sim n\) 的所有排列按字典序排序，这个排列的位次就是它的排名。

他的排名为 $$ \sum_{i=1}^{n} b_{i}*(n-i)+1 $$

其中 \(b_{i}\) 表示在所以还未出现过的数之中有多少个比这个数小

证明如下

设有排列 \(p=a_1,a_2 \dots a_n\) ，那么对任意字典序比 \(p\) 小的排列，一定存在 \(i\) ，使得其前 \(i-1 (1 \le i <n )\) 位与 \(p\) 对应位相同，第 \(i\) 位比 \(p_i\) 小，后续位随意。于是对于任意 \(i\) ，满足条件的排列数就是从后 \(n-i+1\) 位中选一个比 \(a_i\) 小的数、并将剩下 \(n-i\) 个数任意排列的方案数，即为 \(b_i*(n-1)!\) .遍历 \(i\) 即得总方案数 为 $ \sum_{i=1}^{n} b_{i}*(n-i) $ 再加1即为排名。

实现

阶乘预处理一下即可
求 \(b_{i}\) 若使用暴力 总的复杂度是 \(O(n^2)\)
若使用树状数组 总的复杂度是 \(O(n \log n)\)

实现代码如下

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) (-x) & x
const ll mod_ = 998244353;
ll bit[1000010];
int n;
void change(int x, ll delt)
{
    while (x <= n)
    {
        bit[x] += delt;
        x += lowbit(x);
    }
}
ll query(int x)
{
    ll insid = 0;
    while (x)
    {
        insid += bit[x];
        x -= lowbit(x);
    }
    return insid % mod_;
}
ll jie[1100001];
int a[1014514];
void init()//预处理阶乘
{
    jie[0] = 1;
    for (ll oo = 1; oo <= (ll)n; oo++)
    {
        jie[oo] = (jie[oo - 1] * oo) % mod_;
        jie[oo] %= mod_;
    }
}
ll conto()//康托展开
{
    for (int yy = 1; yy <= n; yy++)//加入所有数
    {
        change(a[yy], 1);
    }
    ll insid = 0;
    for (int ww = 1; ww <= n; ww++)
    {
        insid += (query(a[ww] - 1) * jie[n - ww] % mod_) % mod_;//计算排名
        change(a[ww], -1);//将这个数从未出现过的数中删去
        insid %= mod_;
    }
    insid++;
    return insid % mod_;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    init();
    for (int ee = 1; ee <= n; ee++)
    {
        cin >> a[ee];
    }
    cout << conto();
    return 0;
}