Pythonで3×nのボックスを2×1のドミノで埋める方法の数を数えるプログラム

数 n が与えられたとき、3 × n の長方形ブロックを 1 × 2 のドミノ（骨牌）で隙間なく埋める方法が何通りあるかを求めます。ドミノは必要に応じて縦にも横にも回転させて配置できます。答えが非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。

例えば、入力が n = 4 の場合、出力は 11 となります。

解き方のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。まず重要なポイントとして、次のことが挙げられます。

• n が奇数の場合： マスの総数は 3 × n となり奇数になります。しかし、各ドミノは必ず 2 マスを覆うため、奇数個のマスを埋め尽くすことは不可能です。したがって答えは常に 0 になります。
• n が偶数の場合： 幅を 2 ずつ広げながら漸化式で数え上げていきます。

計算では、次の 2 つの状態を管理します。

• cs（complete）： 現在の幅までを完全に埋め尽くす方法の数
• os（other）： 一部が欠けた形状など、途中の配置パターンに対応する方法の数

アルゴリズムの手順は以下のとおりです。

• m = 10^9 + 7 とする
• n が奇数であれば 0 を返す
• cs := 1、os := 0 で初期化する
• i を 2 から n まで 2 ずつ増やしながら繰り返す（※両方の更新式は直前の値を使って同時に計算する）
  • cs := 3 × cs + os
  • os := 2 × cs + os
• cs mod m を返す

実際に値を追ってみると、n = 2 のとき cs = 3、n = 4 のとき cs = 11、n = 6 のとき cs = 41 となり、正しく数え上げられていることが確認できます。計算量は O(n)、必要なメモリは O(1) と非常に効率的です。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n % 2 == 1:
         return 0
      cs = 1
      os = 0
      for i in range(2, n + 1, 2):
         cs, os = (3 * cs + os, 2 * cs + os,)
      return cs % m
ob = Solution()
n = 4
print(ob.solve(n))

入力

4

出力

11