d076: P-6-11. Catalan number
Tags : DP
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:36

Content

Catalan number 的遞迴式定義:

$C_{0} = 1$ and $C_{n} = \sum_{i=0}^{n-1} C_{i}C_{n-1-i}$ for n >= 1.

計算 $C_{n}$除以 P 的餘數。P=1e9+9。

Input

輸入一個非負整數 n,n < 100。

Output

$C_{n}$除以 P 的餘數。

Sample Input
// 1
3
// 2
20
Sample Output
// 1
5
// 2
564120366
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」