#34561: 卡塔蘭數


410446529@gms.tku.edu.tw (Yinya1337)

學校 : 淡江大學
編號 : 173147
來源 : [163.13.52.81]
最後登入時間 :
2024-01-29 13:56:17
d887. 1.山脈種類(chain) -- 99學年度台北市資訊學科能力競賽 | From: [122.116.224.215] | 發表日期 : 2023-03-31 17:43

輸入 = n
可能的山脈數量 = 從(0,0)走到(2n,0)的路徑數量 - 從(0,0)走到(2n,0)且中間經過y<0的路徑數量
.                            = C(2n, n)                                     - C(2n, n+1)
.                            = (1/n+1) * C(2n, n)

詳細證明可以搜尋卡塔蘭數(Catalan number),C++用這個算式小心溢位。

 
ZeroJudge Forum