# ISSC 2022 Problem E

## 題目大意

輸入 $n(1\le n)$，輸出 $1\sim n$ 錯排的數量。一個排列中所有的元素都不在自己原來的位置就被稱為錯排。

## 解法

設 $D_n$ 表示 $1\sim n$ 錯排的數量。已知 $D_1=0,D_2=1$ 。

### 1. 找規律

暴力列出 $n$ 比較小的 case，可以簡單地發現一個規律：

$$D_n=n\times D_{n-1}+(-1)^n$$

### 2. 正經的列狀態轉移式

給一個 $1\sim n-1$ 的錯排，我們可以先把數字 $n$ 排在第 $n$ 個位置，然後把它和 $1\sim n-1$ 的任意數字做交換，都可以產生除一個合法的錯排，透過這樣產生的錯排有 $(n-1)\times D_{n-1}$ 種。

* Ex: $n=5$
$\{2,1,4,3,5\}$ 把 $5$ 和 $1$ 交換後得到錯排 $\{2,5,4,3,1\}$

另一種構造錯排的方式是 $1\sim n-1$ 中只有一個數字排在正確的位置，其餘的數字都是錯排，這樣子的排列種共有 $(n-1)\times D_{n-2}$ 種。接著把數字 $n$ 排在第 $n$ 個位置，然後把它和排在正確的位置的那個數字做交換，因此透過該方法產生的錯排有 $(n-1)\times D_{n-2}$ 種。

* Ex: $n=5$
$\{2,4,3,1,5\}$ 把 $5$ 和 $3$ 交換後得到錯排 $\{2,4,5,1,3\}$

這樣就列舉了 $1\sim n$ 錯排的所有可能，所以狀態轉移式是：

$$D_n=(n-1)\times(D_{n-1}+D_{n-2})$$