天下一プログラマーコンテスト2013予選A

C - 天下一二三パズル


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB


問題文

パズル作家のショウヘイ君は、天下一級のプログラマであるあなたに、「あるパズル」を出題して対決することになった。

そのパズルは以下のようなルールを持つものだった。

  • M \times N のマス目が用意されており、そのマスすべてに対して 1, 2, 3 のいずれかの数字を以下の条件を満たすように入れていく。
  • 同じ行または同じ列にある同じ数字のマスの間には、そのマスの数字以上の個数のマスが存在する。

このパズルでの数字の配置の仕方が何通りあるかを答えよ。
ただし、回転や反転によって同じになる配置も別々のものとして数える。

例えば、3 \times 3 のマス目に対しては以下のような配置ができる。

1

縦または、横一列に 12 つ以上存在している場合は以下のように間に 1 マス以上空いていなければならない。

2
3

2 を配置する場合は 2 マス以上空いていなければならない。

4

入力

入力は以下の形式で標準入力から与えられる。

M N
  • 横方向のマスの数 M と 縦方向のマスの数 N ( 1 \leq M, N \leq 10^6 ) が空白区切りで 1 行で与えられる。

部分点

  • M, N \leq 4 の入力に正解すると、120 点満点に対して部分点として 40 点が与えられる。
  • M, N \leq 100 の入力に正解すると、120 点満点に対して部分点として、さらに 20 点が与えられる。

出力

数字の配置の仕方が何通りあるかを標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。


入力例 1

1 1

出力例 1

3

入力例 2

3 1

出力例 2

8

Source name

天下一プログラマーコンテスト2013 予選A

Submit提出する