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

最近更新 : 2020-12-21 06:52

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=10^9+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
沒有發現任何「解題報告」