题意
初始有一个长为 \(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\)。写出三种情况：
由于第二种情况第一个位置的 ? 让我们不能直接判断三种情况的字典序。因此继续分讨：
其中 \(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;
}
|