← 返回题目列表

AtCoder · pakencamp_2018_day2_e

E. 圣诞树(树着色)

中文机器翻译题面 查看原题

配点: 100 点

問題文

今天是平安夜。 PAKEN为平成时代的最后一个圣诞节制作了以下装饰品。

  • 装饰品由“灯泡”和“棍子”组成。装饰品的制作方法如下。 创建一组满足
  • 電球 (a, b) (0 \leq a \leq D, -a \leq b \leq a) 的整数。a 称为“深度”,b 称为“横坐标”。
  • 電球 (0, 0) 和 按字典顺序比较 (1, -1) 和一个灯泡 直接用棍子绑 (0, 0) 和 按字典顺序比较 (1, 1) 。
  • 同一深度处,横坐标为 1 直接用一根棍子连接仅不同的灯泡。 当
  • 電球 (a, -(a-1)) 和 按字典顺序比较 (a+1, -(a+1)) 和一个灯泡 直接用棍子绑 (a, a-1) 和 按字典顺序比较 (a+1, a+1) 。

例如,D = 1, 2, 3 时,图形将如下图所示。

它看起来像一棵圣诞树。

PAKEN 你就是颜色 我想使用 1 减去 X 最多 X 颜色为所有灯泡着色。但与灯杆直接连接的灯泡颜色不宜相同。
有多少种着色方式? 小于或等于1 \ 000 \ 000 \ 007 请求出除以后的余数。

制約

  • D 是 您也可以写 1 以上 10 \ 000 \ 000 的整数 给出了
  • X 是 您也可以写 1 以上 1 \ 000 \ 000 \ 000 的整数 给出了

入力

输入是按以下格式从标准输入给出的。

D X

出力

有多少种着色方式? 小于或等于1 \ 000 \ 000 \ 007 后的余数打印在一行上。

小課題

小課題 1 [2 点]

输入满足以下条件。

  • D = 1
  • X \leq 4

小課題 2 [12 点]

输入满足以下条件。

  • D \leq 2
  • X \leq 6

小課題 3 [21 点]

输入满足以下条件。

  • D \leq 4
  • X \leq 7

小課題 4 [31 点]

输入满足以下条件。

  • D \leq 50
  • X \leq 25

小課題 5 [18 点]

  • D \leq 50 很满意。

小課題 6 [11 点]

  • D \leq 100 \ 000 很满意。

小課題 7 [5 点]

  • 没有其他限制。

入力例 1

1 2

出力例 1

2

下面 2 绘画有不同的方法。


入力例 2

1 3

出力例 2

18

下面 18 绘画有不同的方法。

该输入是 1 约束。


入力例 3

4 5

出力例 3

101969466

该输入是 2 约束,但存在小问题 满足 3 约束。