前言

也是找到了韩国原题, 有用!

算法

场上有一个比较显然的想法, 即计算出每种逆序对数量对应多少排列, 从而计算出排名第 \(k\) 小的排列有多少个逆序对

但是即使计算出来了, 我们也不好实现, 分析原因发现, 实际上是因为不好确定应该怎么填数, 时间复杂度仍然趋势

一个显然的想法是, 我们在计算出前 \(i\) 位时, 需要相应的的去找后面的解, 那么思路就比较清晰了

首先, 我们需要计算出每种逆序对数量对应多少排列, 考虑 \(\rm{dp}\) (其实我自己不可能考虑的出来, 没有题解的话思考难度应该到 \(\color{#3498db}{提高+/省选−}\))

这个时候 \(\rm{HYH}\) 大佬正在讲这个题, 疑似可以打表找规律, 不管了

首先, 令 \(f_{i, j}\) 表示 \(i\) 个数的排列, 逆序对个数为 \(j\) 的方案数

我们考虑在 \(i - 1\) 的排列中插入 \(i\) 来递推 \(i\) 的状态, 显然的, 我们把 \(i\) 插入在 \(p \in [0, i - 1]\) 这 \(i\) 个位置时, 逆序对个数都会 \(+ (i - p - 1)\)

那么有转移, 注意判断边界条件

时空复杂度都为 \(\mathcal{O} (n \omega)\) , 其中 \(\omega = 200\) , 注意使用前缀和优化, 后面要用 \(i\) 这一维所以不能滚动数组

完事之后考虑推答案,

首先来说, 我们可以考虑从前往后加入数字, 以此来确定第 \(k\) 个全排列
利用先前推出的 \(f\) 数组, 我们可以知道, 每一位产生的逆序对个数, 具体的, 找到最小的逆序对个数 \(j\) , 使得中间经过的逆序对个数严格小于 \(k\)

然后我们就可以知道, 对于从前往后加入的情况, 每次需要制造的逆序对个数

那么我们就可以每次二分插入的数字, 如果制造的逆序对个数 $ < $ 需要制造的逆序对个数, 那么就合法, 并且在这个的基础上尽可能选择更大的数字, 以此得到答案

代码

借用 \(\rm{ZCY}\) 巨佬的代码, 我也确实不太理解

#include <bits/stdc++.h>
using namespace std;
#define int __int128
#define lowbit(x) (x & (-x))
const int N = 1e6 + 5;
int n, fnl[N], s[N];
__int128 sum[300];
__int128 pre[300], k;
vector<vector<__int128>> dp;
__int128 read()
{
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int col[N];
void update(int pos, int w)
{
    for (int i = pos; i <= n; i += lowbit(i))
        s[i] += w;
}
int query(int pos)
{
    int res = 0;
    for (int i = pos; i > 0; i -= lowbit(i))
        res += s[i];
    return res;
}
void write(int x)
{
    if (x >= 10)
        write(x / 10);
    putchar(x % 10 + '0');
}
signed main()
{
    n = read(), k = read();
    dp.resize(n + 2);
    int w = 0;
    if (n <= 21)
        w = 220;
    else if (n <= 100)
        w = 100;
    else
        w = 10;
    for (int i = 0; i <= n; i++)
        dp[i].resize(w + 5);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        pre[0] = dp[i - 1][0];
        for (int j = 1; j <= w; j++)
            pre[j] = pre[j - 1] + dp[i - 1][j];
        for (int j = 0; j < min(i, w); j++)
            dp[i][j] = pre[j];
        for (int j = i; j <= w; j++)
            dp[i][j] = pre[j] - pre[j - i];
    }
    int l = 0, r = 0, ans = 0;
    sum[0] = dp[n][0];
    for (ans = 0; ans <= w; ans++)
    {
        if (ans > 0)
            sum[ans] = sum[ans - 1] + dp[n][ans];
        if (sum[ans] >= k)
            break;
    }
    if (ans)
        k -= sum[ans - 1]; // 在逆序对数相同的排列中的排名
    for (int i = 1; i <= n; i++)
    {
        int tmp = 0;
        for (int j = ans; j >= 0; j--)
        {
            tmp += dp[n - i][j];
            if (tmp >= k)
            {
                k -= tmp - dp[n - i][j];
                col[i] = ans - j + 1; // i 位置上逆序对的个数
                ans = j;
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        update(i, 1);
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = n, ans = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (query(mid) < col[i])
                ans = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        ans++;
        update(ans, -1);
        write(ans), putchar(' ');
    }
    return 0;
}

总结

递推思想的应用