問題一覧 > 通常問題

No.1797 永遠のグリッド

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : ramdosramdos / テスター : maple_1016maple_1016
2 ProblemId : 7408 / 自分の提出
問題文最終更新日: 2022-01-05 04:56:06

問題文

高橋君は、以下の条件を満たすように無限に広がるグリッドを塗りつぶそうと考えています。

  • $H\times W$ のグリッドのパターンの繰り返しで塗りつぶす
  • ちょうど $K$ 色を使う

このような塗り方は何通りありますか。ただし、回転や裏返しは区別しますが、あるパターンを任意の自然数回右もしくは下に平行移動したものは $1$ 通りと数えます。また色は区別できるものとします。

例1:
緑緑青 と 緑青緑 と 青緑緑

は同じパターンです。(右に自然数回移動しています。)

移動により上下左右の範囲外にでたマスは反対側の端に移動します。

例2:
赤青緑   赤緑赤
緑青青 と 青緑赤
赤赤緑   青青緑

は同じパターンです。(右に2回、下に1回平行移動しています。)

入力

$H\ W\ K$

  • $1 \le H \times W \le 10$
  • $1 \le K \le 3$

出力

答えを $1$ 行に出力して下さい。 最後に改行してください。

サンプル

サンプル1
入力
2 3 2
出力
12

■□□ ■■□ ■□□ ■□□
□□□ □□□ ■□□ □■□

■■□ ■□■ ■■■ ■□■
■□□ ■□□ □□□ □■□

□□■ □■■ □■■ □■■
■■■ □■■ ■□■ ■■■

の12パターンです。

サンプル2
入力
1 1 1
出力
1

当然1通りしかありません。

サンプル3
入力
3 3 3
出力
2022

今年は2022年ですね。あけましておめでとうございます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。