> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l4dong-tai-gui-hua/526.-beautiful-arrangement.md).

# 526. Beautiful Arrangement

Suppose you have `n` integers labeled `1` through `n`. A permutation of those `n` integers `perm` (**1-indexed**) is considered a **beautiful arrangement** if for every `i` (`1 <= i <= n`), **either** of the following is true:

* `perm[i]` is divisible by `i`.
* `i` is divisible by `perm[i]`.

Given an integer `n`, return *the **number** of the **beautiful arrangements** that you can construct*.

&#x20;

**Example 1:**

<pre><code><strong>Input: n = 2
</strong><strong>Output: 2
</strong>Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1
</code></pre>

**Example 2:**

<pre><code><strong>Input: n = 1
</strong><strong>Output: 1
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 15`

`分析：`

`dfs + lru_cache+ bit mask`

```
class Solution:
    def countArrangement(self, n: int) -> int:
        @lru_cache(maxsize=None)  
        def dfs(pos,mask):
            if pos == n+1:
                return 1
            res = 0
            for j in range(1,n+1):
                if not mask & (1<<j) and (j%i==0 or i%j==0):
                    res += dfs(i+1, mask | (1<<j))
            return res
        
        return dfs(1,0)

```