問題一覧 > 通常問題

No.1397 Analog Graffiti

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : 👑 evimaevima / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか) iaNTUiaNTU
1 ProblemId : 5884 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-28 20:34:37

問題文

ルンルンは、$N$ 角形のチョコレートが好きです。
あなたは、$R$ 行 $C$ 列に並ぶ $R \times C$ 個の同じ大きさの正方形のピースからなる長方形の板チョコレートを持っています。
この板から、ピース同士の境界に沿って穴のない $N$ 角形のかたまりを一つ切り出す方法は何通りあるでしょうか。
以下の図に、可能な切り出し方とそうでない切り出し方の例を挙げます。

このような $N$ 角形の切り出し方の数を $998244353$ で割った余りを求めてください。

なお、このチョコレートはピースごとに味が微妙に異なり、ルンルンは全てのピースを区別します。
ルンルンが二つの切り出し方を同一とみなすのは、切り出されたピースの集合が一致するときのみです。
(平行移動・回転・反転によって切り出された図形が一致しても、ピースの集合が異なれば別の切り方とみなします。)
また、ルンルンは多角形に内角が $180$ 度であるような頂点の存在を認めないようです。

注記

以下の条件が全て満たされるとき (またそのときに限り)、穴のない $N$ 角形のかたまりが一つ切り出されたとみなします。

  • 切り出されたピース全ての集合を $S$ とする。
    $S$ のどのピースからも、辺を共有する別のピースであって $S$ に含まれるものへの移動を繰り返すことで $S$ の全てのピースに到達可能である。
  • 切り出されなかったピース全ての集合を $T$ とする。
    $T$ のどのピースからも、辺を共有する別のピースであって $T$ に含まれるものへの移動を繰り返すことで板チョコレートの最も外側のピースのいずれかに到達可能である。
  • 切り出されたかたまりの外周を構成するために必要な最小の線分の本数は $N$ 本である。

入力

$R\ C\ N$

  • $1 \leq R \leq 50$
  • $1 \leq C \leq 6$
  • $4 \leq N \leq 50$
  • $R, C$ は整数
  • $N$ は偶数

出力

答えを出力し、末尾で改行してください。

サンプル

サンプル1
入力
2 3 6
出力
16

可能な切り出し方を以下の図に列挙します。

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

可能な切り出し方を以下の図に列挙します。

サンプル3
入力
50 6 50
出力
231109581

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