P8376 [APIO2022] 排列 的一个简短做法
ZYLZPP
·
·
题解
一句话题意
- 构造一个长度 \le 90 的排列，使其递增子序列数（包含空串）为 K(\le 10^{18})。
朴素做法
考虑从小到大加数。
显然（记当前递增子序列数为 ans）：
- 初始：ans = 1（空串）
- 放最前：ans + 1
- 放最后：ans \times 2
则我们得到了一个简单的构造方法：对 K 进行二进制处理即可。
## 优化做法
**注意到 $1.5 \times 60 = 90$（qwq）**。
而 $\times 2$ 的操作是**满的**，不可优化。
这提示我们对 $+1$ 操作进行优化，尝试**合并** $+1$ 操作（一次处理多个二进制 $1$）。
显然 $+1$ 操作每次将**最大**的数添加至最前，所以是**单调递减**的（如图中 **O**）。
| O | | | | |
| :---: | :---: | :---: | :---: | :---: |
| | | | | * |
| | **O** | | | |
| | | | * | |
| | | **O** | | |
而**单调递减**正是 $ans$ 增长较慢的原因（每次只 $+1$）。
考虑将新的数插到第三位（如图中 **X**，注意数是**从小到大**插入的）。
| | | **X** | | | |
| :---: | :---: | :---: | :---: | :---: | :---: |
| **O** | | | | | |
| | | | | | * |
| | **O** | | | | |
| | | | | * | |
| | | | **O** | | |
可使 $ans \to ans + 3$（即一次处理两个二进制 $1$）。
### 综上
记 $K$ 为目标数，则有以下操作：
1. 当 $K \bmod 2 = 0$ 时，将数加到最后，$K \to \frac{K}{2}$。
2. 当 $K \bmod 4 = 1$ 时，先将数放到最前，$K \to K - 1$，再做两次 $1$ 操作。
3. 当 $K \bmod 4 = 3$ 时，先将数放到第三位，$K \to K - 3$，再做两次 $1$ 操作。
4. 注意到 $3$ 操作前须有至少 $2$ 个 $2$ 操作，则可在 $K \le 4$ 时暴力进行 $2$ 操作以保证。
则此时每加 $3$ 个数后 $K$ 至少除以 $4$，$len_{max} = 1.5 \times \log{K} \approx 90$。
## ACcode
```cpp
#include<bits/stdc++.h>
using namespace std;
vector<int > ans;
int n;
void work(long long x) {
if (x <= 4) {
while (--x) ans.insert(ans.begin(), n++);
return;
} //x<=4时暴力+1以保证+1操作数>=2
if (x % 2 == 0) work(x >> 1), ans.push_back(n++);
else if (x % 4 == 1) work(x - 1), ans.insert(ans.begin(), n++);
else if (x % 4 == 3) work(x - 3), ans.insert(ans.begin() + 2, n++);
}
vector<int > construct_permutation(long long k) {
ans.resize(n = 0);
work(k);
return ans;
}
```
感谢审核，辛苦 : ) 。