主題
題目連結(jié)：
題目大意：
給定一正整數(shù) Ｎ（Ｎ ≦ ８００），代表原本有Ｎ個(gè)物件，編號(hào)為 １ ～ Ｎ ，排在 １ ～ Ｎ 的位置。
求重新排列，使得 Ｎ 個(gè)物件都不在自己原來的位置上（也就是「錯(cuò)排」）的方法數(shù)為何？
當(dāng) Ｎ ＝ －１ 時(shí)，代表輸入結(jié)束。
範(fàn)例輸入：
1
2
3
4
-1
範(fàn)例輸出：
0
1
2
9
解題思維：
當(dāng)窮舉方法數(shù)的時(shí)候，乍看之下可能沒有什麼規(guī)律。但是仔細(xì)觀察可以發(fā)現(xiàn)，一些疑似遞迴的蹤跡。
考慮以下情況，當(dāng) Ｎ ≧ ３時(shí)：
有鑑於第 Ｎ 個(gè)數(shù)字不會(huì)排在第 Ｎ 個(gè)位置，一定會(huì)放在１ ～ Ｎ－１其中之一。這時(shí)，它放的位置假設(shè)為 Ｋ ，而 Ｋ 放的地方有兩種情形。
第一種， Ｋ 放在 Ｎ 的位置，也就是 Ｎ、Ｋ 位置互換。那麼，剩下的Ｎ－２個(gè)數(shù)字之原本的位置也就都尚未被占去。因此這個(gè)情況等價(jià)於 Ｎ－２ 時(shí)的方法數(shù)。
第二種， Ｋ 沒有放在 Ｎ 的位置。由於我們已經(jīng)把 Ｎ 放在 Ｋ 的位置，而Ｋ絕對(duì)不會(huì)放在Ｎ的位置。我們把放在 Ｋ 位置的Ｎ拿掉，剩下的物件就像是 Ｎ－１ 時(shí)的情況之排列（Ｋ就變成了新的Ｎ）。因此等價(jià)於 Ｎ－１ 時(shí)的方法數(shù)。
又因?yàn)椋畏诺臅r(shí)候，可以從１ ～ Ｎ－１任意挑一個(gè)位置放（也就是Ｋ是其中任意數(shù)字）。因此Ｋ有Ｎ－１種可能挑法。
所以， Ｎ 的方法數(shù) ＝ （Ｎ－１）*（Ｎ－１的方法數(shù) ＋ Ｎ－２的方法數(shù)）。
而又因?yàn)椋慰傻剑福埃暗木壒剩虼松鲜鲞f迴式的值會(huì)增長(zhǎng)到突破Ｃ＋＋的整數(shù)型態(tài)上限，為此，我們需要大數(shù)運(yùn)算，詳見這裡。
達(dá)人
