令 X 表示正確的括號表示式。X 的內容為僅含 '(' 和 ')' 的字串。定義如下:
例如:以下的字串都是正確的括號表示式(所以當然屬於 X)
()(())()
(()(()))
而以下的字串不是正確的括號表示式(所以當然不屬於 X)
(()))(()
())(()
令 E 是一個正確的括號表示式(因此 E 屬於 X)。
E 的長度為字串的長度。
而 E 的深度 D(E) 被定義如下:
ì 0 如果
E 是空字串
D(E)= í
D(A)+1 如果 E = (A), 並且
A 屬於 X
î max(D(A),D(B)) 如果
E = AB, 並且 A, B 都屬於
X
例如:“()(())()” 的長度是 8 , 而深度為 2 。
給你 n 和 d ,你的任務是找出長度為 n,且深度為 d 的所有正確的括號表示式共有多少個。
例如: n=6, d=2 共有以下3種正確的括號表示式。
(())()
()(())
(()())
Input
每組測試資料一列,含有 2 個整數 n 和 d(2 <= n <= 300,1 <= d <= 150)。
輸入不會超過 20 列,但可能含有空白列,你不用理會這些空白列。
Output
對每一組測試資料輸出一列。長度為 n,且深度為 d 的所有正確的括號表示式共有多少個。
| Sample Input | Sample Output |
6 2 300 150 100 2 100 4 100 19 10 1 10 2 10 3 10 4 10 5 |
3 1 562949953421311 119430741619474209626016 10441348575948087788919740 1 15 18 7 1 |