4 人解决,5 人已尝试。
5 份提交通过,共有 27 份提交。
7.7 EMB 奖励。
单点时限: 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}$ 的正整数。
2 5
1 4 6
3 5
1 4 6 12
4 人解决,5 人已尝试。
5 份提交通过,共有 27 份提交。
7.7 EMB 奖励。