← 返回题目列表

AtCoder · ndpc2026_a

A. 多联骨牌

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

分数: 2 点

问题陈述

您拥有无限数量的以下两种类型的多骨牌:

  • 大小为矩形的多骨骨牌 2 (高度)× 1 (宽度)
  • 通过去除一个而形成的 L 形多骨骨牌 1 \times 1 方形 2 \times 2 广场

给你一个尺寸的网格 2 (高度)× N (宽度)。您希望在以下条件下使用这些多骨牌完全平铺网格的所有单元格:

  • 网格的每个单元格必须恰好被一个多联骨牌覆盖。
  • 放置多骨牌时您可以旋转它们。

找出满足这些条件的多骨牌的放置方式的数量。请注意,即使可以通过旋转或翻转整个网格从另一种获得一种排列,两种排列也被视为不同。而且,相同形状的多骨牌是无法区分的。

约束

  • 1 \leq N \leq 40
  • N 是一个整数

输入

输入由标准输入给出,格式如下:

N

输出

打印有效平铺的数量。


示例输入 1

3

示例输出 1

5

有 5 有效的平铺如下所示。

image


示例输入 2

40

示例输出 2

25366833951139