3224. 帕斯卡金字塔

单点时限: 2.0 sec

内存限制: 256 MB

$D$ 维的帕斯卡金字塔,是一个具有如下定义的函数:

$$C(x_1, x_2, \ldots, x_D) =
\begin{cases}
1, & {x_i = 0, \forall 1 \leq i \leq D} \
0, & {x_i < 0, \exists 1 \leq i \leq D} \
C(x_1-1, x_2, \ldots, x_D) + C(x_1, x_2-1, \ldots, x_D) \ + \ldots + C(x_1, x_2, \ldots, x_D - 1), & otherwise
\end{cases}$$

我们定义高度为 $H$ 的金字塔,为所有点满足约束条件 $\forall 1 \leq i \leq D, 0 \leq x_i < H \land x_1 + x_2 + \ldots + x_D \leq H - 1$ 的金字塔。该金字塔的底层,为其中满足 $x_1 + x_2 + \ldots + x_D = H$ 的点。

为了方便理解,下面解释 $D=2$ 和 $D=3$ 时的特例。

帕斯卡三角形,又称杨辉三角,是帕斯卡金字塔在 $D=2$ 时的特例。取 $H=5$,可得下面的情况:

其中加粗的部分是金字塔的底层。

三维的情况略复杂一些,涉及三个变量:$x, y, z$,同样取 $H=5$。

以 $x=1, y=2, z=1$ 为例,$(1,2,1)$ 的值是 $(0,2,1)$,$(1,1,1)$ 和 $(1,2,0)$ 的和,也就是 $6+3+3=12$。金字塔的底层是满足 $x+y+z=4$ 的部分,即加粗的部分。

本题的任务是要对给定的 $D$ 和 $H$,输出帕斯卡金字塔底层的函数值形成的集合,即:${C(x_1, \ldots, x_D) | 0 \leq x_i < H \land \sum_i x_i = H - 1}$。

输入格式

一行两个整数,$D, H$ $(2 \leq D < 32, 1 \leq H < 32)$。

输出格式

将集合中的数从小到大输出出来,一行一个整数,不带重复。输入保证输出结果都是小于 $2^{63}$ 的正整数。

样例

Input
2 5
Output
1
4
6
Input
3 5
Output
1
4
6
12

4 人解决,4 人已尝试。

5 份提交通过,共有 15 份提交。

9.6 EMB 奖励。

创建: 3 年,5 月前.

修改: 3 年,1 月前.

最后提交: 1 年,4 月前.

来源: Southwestern European 2016

题目标签