竹園論壇

標題: [數學][排容]1086 - 放錯的信封 [打印本頁]

作者: Shaymin 時間: 2014-9-25 20:36
標題: [數學][排容]1086 - 放錯的信封
本帖最後由 Shaymin 於 2014-9-25 22:29 編輯

題目：http://tioj.ck.tp.edu.tw/problems/1086
測試結果：http://tioj.ck.tp.edu.tw/submissions/2768

純粹的排組數學題，公式如下：
[tex]%5Cdpi%7B200%7D%20%5Cfn_cs%20%5Csum_%7Bi%3D0%7D%5E%7BN%7D%5ENC_i%28N-i%29%21%28-1%29%5Ei[/tex]

詳情請問你的數學老師，記得用long long。

作者: Sylveon 時間: 2014-9-26 12:53
提供使用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]

歡迎光臨竹園論壇 (http://forum.tfcis.org/)