解題說明
Beautiful Arrangement
題目描述：假設你有 n 個整數，分別是 1 到 n。若一個由這 n 個整數組成的排列，對每個位置 i（1-indexed）都滿足下列其中一個條件，則稱為「美麗排列」：
perm[i]能被i整除，或i能被perm[i]整除。
給定整數 n，回傳美麗排列的數量。
解題思路：使用回溯法逐位置（從位置 1 到 n）決定放哪個數字。在每個位置嘗試所有尚未使用的數字，若滿足整除條件則遞迴至下一位置，否則剪枝跳過。用一個整數 used（位元遮罩）追蹤已使用的數字，第 i 位為 1 表示數字 i+1 已使用，位元操作使已用數字的檢查與標記均為 O(1)。
由於 n ≤ 15，位元遮罩最多 15 位，結合回溯剪枝，實際搜尋空間遠小於 n!，效率極佳。也可搭配記憶化（memo[used] 記錄從當前位置開始的方案數），避免重複計算相同的 (position, used) 狀態。
C++ 解法
複雜度分析
時間複雜度：O(k)，其中 k 為實際訪問的狀態數。最壞為 O(n!)，但由於整除條件剪去大量分支，實際遠小於此；n=15 時約幾千個遞迴呼叫。若加記憶化，狀態數上界為 O(n × 2^n)。
空間複雜度：O(n)——遞迴深度為 n，每層使用 O(1) 額外空間（位元遮罩存於整數）。若加記憶化則為 O(n × 2^n)。
虛擬碼
1. Initialize count = 0.
2. Call backtrack(n, pos=1, used=0, count).
3. In backtrack(n, pos, used, count):
a. If pos > n: increment count and return.
b. For num from 1 to n:
- If bit (num-1) is set in used: skip.
- If num % pos == 0 OR pos % num == 0:
* Set bit (num-1) in used.
* Recurse: backtrack(n, pos+1, used, count).
* Unset bit (num-1) in used (implicit since used is passed by value).
4. Return count.其他解法
方法一：記憶化搜尋（Bitmask DP）
dp[mask] 表示「已放置的數字集合為 mask 時，從當前位置（= popcount(mask) + 1）開始能形成的美麗排列數」。狀態數 O(2^n)，每個狀態 O(n) 轉移，整體 O(n × 2^n)。由於 n ≤ 15，2^15 = 32768，非常快。此法在 n 較大時更穩定，避免回溯的重複計算。
方法二：純暴力全排列
枚舉 1..n 的所有排列（用 next_permutation），對每個排列驗證所有位置是否滿足整除條件。時間複雜度 O(n! × n)，n=15 時超過十兆次操作，完全不可行，但邏輯最清晰，適合理解題意。
方法三：迭代式 Bitmask DP（Bottom-up）
從空集合 mask=0 開始，逐步擴展：對每個 mask，確定下一個位置 pos = popcount(mask)+1，嘗試所有未在 mask 中且滿足整除條件的數字 num，更新 dp[mask | (1 << (num-1))]。不使用遞迴，適合避免函數呼叫開銷的場景。
延伸思考
- 若條件改為「perm[i] 與 i 互質（gcd(perm[i], i) == 1）」，回溯的合法性檢查應如何修改？預計答案數量會如何變化？
- n = 15 是本題的上限，若 n 增大到 20，記憶化搜尋的記憶體需求（O(2^20 × 20)）是否仍然可接受？有什麼方法可以壓縮空間？
- 如何修改程式以輸出所有美麗排列本身（而非僅計數）？此時時間複雜度由什麼因素主導？