No.1397 Analog Graffiti
タグ : / 解いたユーザー数 13
作問者 :
evima
/ テスター :
夕叢霧香(ゆうむらきりか)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。