主題
題目連結：
題目大意：
給定一正整數 Ｎ（Ｎ ≦ ８００），代表原本有Ｎ個物件，編號為 １ ～ Ｎ ，排在 １ ～ Ｎ 的位置。
求重新排列，使得 Ｎ 個物件都不在自己原來的位置上（也就是「錯排」）的方法數為何？
當 Ｎ ＝ －１ 時，代表輸入結束。
範例輸入：
1
2
3
4
-1
範例輸出：
0
1
2
9
解題思維：
當窮舉方法數的時候，乍看之下可能沒有什麼規律。但是仔細觀察可以發現，一些疑似遞迴的蹤跡。
考慮以下情況，當 Ｎ ≧ ３時：
有鑑於第 Ｎ 個數字不會排在第 Ｎ 個位置，一定會放在１ ～ Ｎ－１其中之一。這時，它放的位置假設為 Ｋ ，而 Ｋ 放的地方有兩種情形。
第一種， Ｋ 放在 Ｎ 的位置，也就是 Ｎ、Ｋ 位置互換。那麼，剩下的Ｎ－２個數字之原本的位置也就都尚未被占去。因此這個情況等價於 Ｎ－２ 時的方法數。
第二種， Ｋ 沒有放在 Ｎ 的位置。由於我們已經把 Ｎ 放在 Ｋ 的位置，而Ｋ絕對不會放在Ｎ的位置。我們把放在 Ｋ 位置的Ｎ拿掉，剩下的物件就像是 Ｎ－１ 時的情況之排列（Ｋ就變成了新的Ｎ）。因此等價於 Ｎ－１ 時的方法數。
又因為Ｎ放的時候，可以從１ ～ Ｎ－１任意挑一個位置放（也就是Ｋ是其中任意數字）。因此Ｋ有Ｎ－１種可能挑法。
所以， Ｎ 的方法數 ＝ （Ｎ－１）*（Ｎ－１的方法數 ＋ Ｎ－２的方法數）。
而又因為Ｎ可到８００的緣故，因此上述遞迴式的值會增長到突破Ｃ＋＋的整數型態上限，為此，我們需要大數運算，詳見這裡。
達人
