[數學][排容]1086 - 放錯的信封

Sylveon

提供使用DP的解法
AC：http://tioj.ck.tp.edu.tw/submissions/2811



令[tex]f(n)[/tex]表示信件數量為N時有幾種放法。根據題目定義，信件K不可以放在第K個信封裡，在這裡以箱子Pos及數字代替。

求[tex]f(n+1)[/tex]

要把第[tex]n+1[/tex]封信放到Pos T有n種方法。
1.令T不可以放在Pos n+1，則可以變成有n個信封不可放於原位的問題，共有[tex]f(n)[/tex]種可能。
2.但是T其實可以放在Pos n+1，即是把T和n+1互換位置，剩下的n-1封信有[tex]f(n-1)[/tex]種方法，要加回去。


總方法數[tex]%3Df%28n+1%29%3Dn%5Ctimes%20%28f%28n%29+f%28n-1%29%29[/tex]

遊客，本帖隱藏的內容需要積分高於 100 才可瀏覽，您當前積分為 0