問題一覧 > 通常問題

No.1397 Analog Graffiti

レベル : / AI推定難易度 : 3000 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 13
作問者 : evima / テスター : 夕叢霧香(ゆうむらきりか) iaNTU
お気に入りにしたユーザー ProblemId : 5884 / 自分の提出
問題文最終更新日: 2021-02-28 20:34:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
バレンタインコンテスト2021 (順位表) の他の問題:

Problem Statement

Runrun likes $N$-gonal chocolates.
You have a rectangular chocolate bar consisting of $R \times C$ square pieces of the same size, arranged in $R$ rows and $C$ columns.
How many ways are there to cut out from this bar a single $N$-gonal chunk without holes, along the boundaries between pieces?
The figure below shows examples of cuts that are possible and cuts that are not.

Find the number of such ways to cut out an $N$-gon, modulo $998244353$.

Note that the flavor of this chocolate differs subtly from piece to piece, and Runrun distinguishes all the pieces.
Runrun considers two ways of cutting to be the same only when the sets of cut-out pieces coincide.
(Even if the cut-out shapes coincide under translation, rotation, or reflection, they are considered different ways of cutting if the sets of pieces differ.)
Also, Runrun apparently does not accept the existence of vertices with an interior angle of $180$ degrees in a polygon.

Notes

A single $N$-gonal chunk without holes is considered to have been cut out if and only if all of the following conditions are satisfied.

  • Let $S$ be the set of all cut-out pieces.
    From any piece of $S$, every piece of $S$ can be reached by repeatedly moving to another piece that shares an edge with the current one and is contained in $S$.
  • Let $T$ be the set of all pieces that were not cut out.
    From any piece of $T$, one of the outermost pieces of the chocolate bar can be reached by repeatedly moving to another piece that shares an edge with the current one and is contained in $T$.
  • The minimum number of line segments required to form the perimeter of the cut-out chunk is $N$.

Input

$R\ C\ N$

  • $1 \leq R \leq 50$
  • $1 \leq C \leq 6$
  • $4 \leq N \leq 50$
  • $R, C$ are integers.
  • $N$ is even.

Output

Output the answer, followed by a newline.

Sample

Sample 1
Input
2 3 6
Output
16

The figure below lists all possible ways of cutting.

Sample 2
Input
3 3 12
Output
7

The figure below lists all possible ways of cutting.

Sample 3
Input
50 6 50
Output
231109581

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