跳转至

250610 模拟赛 T1 题解

题意

初始有一个长为 \(n\) 的排列,满足 \(a_i=i\)。称另一个排列 \(p\) 是合法的当且仅当它可以由 \(a\) 经过 \(n\) 次操作得到;在第 \(i\) 次操作时,你可以选择一下三种的任意一种执行:

  • 找到数字 \(n-i+1\)\(p\) 中出现的位置 \(j\),若 \(j\ne 1\),你可以交换 \(p_j\)\(p_{j-1}\)
  • 找到数字 \(n-i+1\)\(p\) 中出现的位置 \(j\),若 \(j\ne n\),你可以交换 \(p_j\)\(p_{j+1}\)
  • 什么都不做;

\(q\) 次询问,每次询问给定 \(n,k\),问所有合法的排列中字典序第 \(k\) 小的排列是什么。

\(\sum{n}\le 2\times 10^5,\ k\le 10^{18}\)

题解

考虑试填法,我们需要知道当前位置可以填哪些字符,以及对应的方案数。通过手玩数据我们能发现 \(p\) 中数字 \(1\) 出现的位置不会太靠后,只能位于 \(p_1,p_2,p_3\)。写出三种情况:

1 ?
? 1 ?
2 ? 1 ?

由于第二种情况第一个位置的 ? 让我们不能直接判断三种情况的字典序。因此继续分讨:

1 ?
2 1 ?
2 ? 1
x 1 ?

其中 \(x>2\)。注意到,? 部分经过偏移之后可以形成一个子问题。

先考虑计数,设 \(f_{0,n}\) 表示长为 \(n\) 的合法排列数量,\(f_{1,n}\) 表示长为 \(n\) 且第一位是 \(1\) 的合法排列数量。根据子问题转化的性质,我们可以写出转移:

\[ \begin{align*} f_{0,n}=f_{0,n-1}+2f_{0,n-2}+(f_{0,n-1}-f_{1,n-1})\\ f_{1,n}=f_{0,n-1} \end{align*} \]

显然可以简化成一个维度的式子:

\[ f_{n}=2f_{n-1}+f_{n-2} \]

这样,我们通过 \(O(n)\) 的预处理就可以解决计数的问题。试填的时候我们记一个 tag 表示当前子问题的第一个位置能不能填 \(1\) 即可。

AC 代码
#include<iostream>
#include<cassert>
#define int long long
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int INF2 = 1e18;

int T;
int n, k;

int f[N];

void dfs(int n, int k, int b, int res[], bool tag = 0) {
    if(n == 0) {
        assert(k == 1);
        return;
    }
    if(n == 1) {
        assert(k == 1);
        res[1] = 1 + b;
        return;
    }
    if(!tag && k <= f[n - 1]) {
        res[1] = 1 + b;
        dfs(n - 1, k, b + 1, res + 1);
        return;
    } else if(!tag) k -= f[n - 1];
    if(k <= f[n - 2]) {
        res[1] = 2 + b;
        res[2] = 1 + b;
        dfs(n - 2, k, b + 2, res + 2);
        return;
    } else k -= f[n - 2];
    assert(n - 2 > 0);
    if(k <= f[n - 2]) {
        res[1] = 2 + b;
        res[2] = 1 + b;
        dfs(n - 2, k, b + 2, res + 2);
        swap(res[2], res[3]);
        return;
    } else k -= f[n - 2];
    if(k <= f[n - 1] - f[n - 2]) {
        res[1] = 1 + b;
        dfs(n - 1, k, b + 1, res + 1, 1);
        swap(res[1], res[2]);
        return;
    }
    throw;
}

int res[N];

signed main() {

    f[1] = 1;
    for(int i = 2; i < N; i++) {
        if(f[i - 1] >= INF2) f[i] = INF;
        else f[i] = 2 * f[i - 1] + f[i - 2];
    }
    f[0] = 1;

    cin >> T;
    while(T--) {
        cin >> n >> k;
        if(k > f[n]) { cout << "-1\n"; continue; }
        dfs(n, k, 0, res);
        for(int i = 1; i <= n; i++) {
            cout << res[i] << ' ';
        }
        cout << '\n';
    }

    return 0;
}