UVa 369 Combinations

解題策略

組合公式: C(n,r) = n! / (n-r)!r!
直接使用組合公式來計算結果就可以了。

必須注意的就是階乘的成長速度極快,14! 的值就已經超出long的範圍,更別說第一個範例測資 C(100,6),100!保證爆掉。所以不能分開計算分子分母最後再相除,要在迴圈中邊乘邊除,壓低計算過程中的數字。

注意

要用浮點數,因為除法會產生小數點。ZeroJudge的測資更嚴苛些,想通過最好把變數精確度提高到long double。而long double與printf溝通的代號是%Lf

碎碎念

偷懶寫的遞迴解法,果然製造 Time Limit Exceeded。自己測了一下,C(34,20)要跑個十來秒,數量級成長很恐怖呀。(汗)


留言

  1. 這題用DP要怎麼寫?
    100取6還可以計算
    但是到了100取7的時候數字就變成負數了..
    請問..
    有辦法解決嗎?

    回覆刪除
  2. 第一個想法就是recursive, 不過C(100,50) 100取50就爆炸了。
    DP的想法就是把rescursive重複計算的部分先 "記" 起來,
    所以直些把所有取法先算完..

    C(0,0) C(1,0) C(2,0) ... C(100,0)
    C(1,1) C(2,1) ... C(100,1)
    C(2,2) ... C(100,2)
    ...
    C(n,m) = C(n-1,m-1) + C(n-1,m) (n > m)
    用這個只會花O(n^2)時間跟空間開始建表,之後查詢O(1)

    Source code: https://bitbucket.org/Menggen/uva/src/e9954c9722df5415c3801b3f027eb059744a8217/UVa/acm_369.cc?at=master

    回覆刪除

張貼留言

這個網誌中的熱門文章

UVa 10125 Sumsets

讀書心得: 撒哈拉的故事

讀書心得: 你以為你以為的就是你以為的嗎?