luogu#P2270. [HNOI2002] 奶牛的运算

[HNOI2002] 奶牛的运算

题目描述

最近,Farmer John 农场里的奶牛正在学习数学基础课。这天,奶牛 Besty 学会了加减法运算和括号的使用。

Farmer John 为了考察 Besty 的学习情况,写了如下一个算式:

S=A1A2AnS =A_1-A_2-\ldots-A_n

接着,Farmer John 告诉 Besty,这个算式中省略了 KK 个括号。将这 KK 个括号加入该算式中,就会得到一种算式方案。

例如:S=A1A2A3A4S=A_1-A_2-A_3-A_4K=2K = 2,则 S=(A1)A2(A3A4)S = (A_1)-A_2 - (A_3- A_4) 就是一种算式方案。

而对任意两个算式方案,SS'SS'' 本质不同是指:存在某数列 A1,,AnA_1,\ldots,A_n 满足 SSS'\ne S''。否则就是本质相同。

例如:S=(A1)A2(A3A4)S'=(A_1)-A_2-(A_3-A_4)S=(A1A2)(A3A4)S''=(A_1-A_2)-(A_3-A_4) 就是本质相同的算式方案。

现在,Farmer John 告诉奶牛 Besty 算式中项的个数 NN 和括号的个数 KK(数列 AA 是变量,我们不需要关心它),他想考考 Besty 究竟有多少本质不同的算式方案。

输入格式

输入文件仅一行,依次为两个整数 NNKK。(1<N,K<1001<N,K<100)。

输出格式

输出文件仅一行,为本质不同的算式方案数。

4 1
4