QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 1024 MB 満点: 100

#3202. 帕斯卡超金字塔

統計

我们程序员都熟悉并喜爱帕斯卡三角形:一个数字数组,顶部为 1,每个条目是其正上方两个数字之和(两端的数字除外,它们始终为 1)。为了对这个生成规则进行编程,三角形最好表示为左对齐形式;此时左列和顶行的数字均为 1,其他每个数字都是其上方和左侧数字之和。下图中加粗的数字对应高度为 5 的帕斯卡三角形的底边:

帕斯卡超金字塔(Pascal's hyper-pyramids)将三角形推广到了更高维度。在 3 维空间中,位置 $(x, y, z)$ 处的值是以下三个位置的值之和:

  • $(x, y, z - 1)$,如果不在底面($z = 0$),则为正下方的数值;
  • $(x, y - 1, z)$,如果不在背面($y = 0$),则为正后方的数值;
  • $(x - 1, y, z)$,如果不在左侧面($x = 0$),则为正左方的数值。

下图展示了通过固定 $z$ 坐标的值,将高度为 5 的帕斯卡 3D 金字塔切片得到的平面序列:

例如,位置 $x = 1, y = 2, z = 1$ 处的数字是位置 $(0, 2, 1)$、$(1, 1, 1)$ 和 $(1, 2, 0)$ 处数值之和,即 $6 + 3 + 3 = 12$。金字塔的底边对应于满足 $x + y + z = 4$ 的位置平面(如上图加粗所示)。

每一层的大小随金字塔高度呈二次方增长,但由于对称性,存在许多重复的值:位置互为排列的坐标点上的数字必须相等。例如,上述位置 $(0, 1, 2)$、$(1, 2, 0)$ 和 $(2, 1, 0)$ 处的数字均等于 3。

任务

编写一个程序,给定超空间的维度数 $D$ 和超金字塔的高度 $H$,计算底边上的数字集合。

输入格式

一行,包含两个正整数:维度数 $D$ 和超金字塔的高度 $H$。

数据范围

$2 \le D < 32$ 维度数 $1 \le H < 32$ 高度 $D$ 和 $H$ 满足超金字塔中的所有数字均小于 $2^{63}$。

输出格式

输出超金字塔底边的数字集合,不包含重复项,每行一个数字,按升序排列。

样例

样例输入 1

2 5

样例输出 1

1
4
6

样例输入 2

3 5

样例输出 2

1
4
6
12

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.