查看: 941|回復: 1

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

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-2-12 11:21
  • 簽到天數: 2 天

    [LV.1]初來乍到

    18

    主題

    31

    帖子

    211

    積分

    好好學生

    Rank: 3Rank: 3

    積分
    211
    發表於 2014-9-25 20:36:53 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 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
    遊客,本帖隱藏的內容需要積分高於 100 才可瀏覽,您當前積分為 0

    評分

    參與人數 1金幣 +2 收起 理由
    Sylveon + 2

    查看全部評分

    回復

    使用道具 檢舉

  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2014-9-26 12:53:09 | 顯示全部樓層
    提供使用DP的解法
    AC:http://tioj.ck.tp.edu.tw/submissions/2811

    1086dp.png

    令[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

    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表