2011年3月12日 星期六

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)要跑個十來秒,數量級成長很恐怖呀。(汗)