今天我們來看看CF553B 題目連結
題目描述
給定一個長度為 $n$ 的排列 $p = [p_1, p_2, \dots, p_n]$（由 $1$ 到 $n$ 的互不相同的整數組成），我們可以將其分解成若干個循環，每個循環表示數字之間的映射關係。具體地，對於一個循環：
- 將循環內的元素重新排列，使得最大的元素位於第一位；
- 將所有循環按照其第一個元素（也就是每個循環中的最大元素）從小到大排序；
- 將標準循環表示法中的括號去除後，得到一個新的排列。
如果一個排列在經過上述操作後保持不變，則稱這個排列為「穩定排列」。Kyoya 將所有長度為 $n$ 的穩定排列按照字典序排序，並希望重現這個序列。給定 $n$ 和 $k$，請求出字典序中第 $k$ 個穩定排列。
輸入格式
第一行包含兩個整數 $n$ 與 $k$ ($1 \leq n \leq 50,\ 1 \leq k \leq \min{10^{18}, l}$)，其中 $l$ 表示所有穩定排列的總數。
輸出格式
輸出一個包含 $n$ 個整數的排列，各數字之間以空格分隔，即字典序中第 $k$ 個穩定排列。
前言
沒想到居然由我自己想出來了，我還特地回去看我以前代數筆記複習permutation有什麼性質，結果其實沒什麼用🤣🤣
這題我特地用正常一點的方式寫code，沒有用我的macro那些亂七八糟的什麼rep,per,pb,ll,SZ(),VI
其實也還好，反正寫LeetCode也都這樣寫
想法
寫這題讓我對permutation的認識更清晰了，我原本連到底要怎麼把一個permutation變成cyclic presentation都不知道。
建議可以學題目敘述這樣看一個permutation：
對於$\sigma=(4,1,6,2,5,3)$，我們看成一個Graph：
$$
\begin{aligned}
1\rightarrow 4\
2\rightarrow 1\
3\rightarrow 6\
4\rightarrow 2\
5\rightarrow 5\
6\rightarrow 3
\end{aligned}
$$
可以畫成這樣：
也就是$p=(4,1,6,2,5,3)=(4,2,1)(5)(6,3)$
然後我們來看看如果題目要求的條件成立，會怎麼樣：
假設$p=(p(1),p(2),p(3),p(4))$，先來看看如果$p=(p(1),p(2))(p(3),p(4))$
代表$p(3)>p(4)>p(1)>p(2)$
圖會長這樣：
同時圖也會長這樣：
所以代表$p(2)=1,p(1)=2,p(3)=4,p(4)=3$
我們再來看$n=5$的情況：
假設$p=(p(1),p(2),p(3),p(4),p(5))=(p(1),p(2),p(3))(p(4),p(5))$
以下兩張圖同時成立：
因此會發現，$p(3)=1,p(2)=3,p(1)=2$
然而根據題目條件，我們應該要有$p(4)>p(5)>p(1)>p(2)>p(3)$，我們現在違反了！
稍微觀察，會發現同個cycle裡的$(p(i),p(i+1),p(i+2))$，其實就會是$(i+1,i+2,i)$，但是$i+1<i+2$，違反題目的條件。
因此，我們發現只有$2-$cycle或者$1-$cycle(像是(5)就是$1-$cycle)是可能滿足題目條件的。
因此我們現在題目的解法就是，對於$p=(1,2,3,…)$，我們要找到第$k$個字典序的$1-,2-$cycle排列順序。
對於長度$n$的序列，要怎麼求有幾種分配$1-,2-$cycle的方法呢？我們可以用dp，轉移式是：
$$
\text{dp}[i] = \text{dp}[i-2] + \text{dp}[i-1]
$$
$\text{dp}[i]$代表長度為$i$的序列有幾種分配方式。(也可以發現這其實就是斐波那契數列)
知道這個以後，我們也知道，如果你現在可以選擇用$1-$cycle或者$2-$cycle，$1-$cycle字典序是比較小的，因為最前面的數字比較小。
所以我們假設已經看完前$i$個數字了，如果排$1-$cycle剩下的可能cycle分配方式會$>=k$，那就答案放入一個$1-$cycle；反之如果剩下的可能cycle分配方式會$<k$，我們就把$k$減掉「排$1-$cycle剩下的可能cycle分配方式」，然後答案放入一個$2-$cycle。
程式碼:
const int _n = 51;
ll n, k, possibility[_n];
main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
// 1-indexed
possibility[0] = 1;
possibility[1] = 1;
possibility[2] = 2;
for (int i = 3; i <= n; i++) {
possibility[i] = possibility[i - 1] + possibility[i - 2];
}
vector<int> ansseq; // 1 for 1 cycle, 2 for 2 cycle
ll k2 = k;
int i = 0;
while (i < n) {
// i = idx before making new cycle length decision
if (possibility[n - i - 1] >= k2) {
ansseq.push_back(1);
i += 1;
} else {
k2 -= possibility[n - i - 1];
ansseq.push_back(2);
i += 2;
}
}
vector<int> ans;
for (int i = 1; i <= n; i++) {
ans.push_back(i);
}
int idx = 0;
for (int i = 0; i < (int)ansseq.size(); i++) {
if (ansseq[i] == 1) {
idx++;
} else {
swap(ans[idx], ans[idx + 1]);
idx += 2;
}
}
for (int x : ans) {
cout << x << ' ';
}
cout << '\n';
return 0;
}
標頭、模板請點Submission看 Submission