/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 H 行、横 W 列のマス目があり、それぞれのマスには 1 から 9 のいずれかの数字が書かれています。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす整数の組 (i, j) それぞれについて、上から i 行目、 左から j 列目のマスに書かれた数字は c_{i, j} です。
高橋君と青木君はこのマス目を使って 2 人で遊びます。 まず、高橋君がいずれか 1 つのマスを選び、そのマスにコマを置きます。その後、2 人は下記の手順 1. から 4. を N 回繰り返します。
- 高橋君が次の 2 つのうちどちらか一方を行う。
- 現在コマが置かれているマスと同じ行にある別のマスに、コマを移動する。
- 何もしない。
- 高橋君が、現在コマが置かれているマスに書かれた数字を黒板に書く。
- 青木君が次の 2 つのうちどちらか一方を行う。
- 現在コマが置かれているマスと同じ列にある別のマスに、コマを移動する。
- 何もしない。
- 青木君が、現在コマが置かれているマスに書かれた数字を黒板に書く。
その後、黒板には 2N 個の数字が書かれています。それらの数字を黒板に書かれたのが早い順番に並べたものを d_1, d_2, \ldots, d_{2N} とします。 2 人は 2N 個の数字をこの順番で繋げて 2N 桁の整数 X := d_1d_2\ldots d_{2N} を作ります。
整数 X としてあり得るものが何通りあるかを、998244353 で割った余りを出力してください。
制約
- 2 \leq H, W \leq 10
- 1 \leq N \leq 300
- 1 \leq c_{i, j} \leq 9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W N
c_{1, 1}c_{1, 2}\cdotsc_{1, W}
c_{2, 1}c_{2, 2}\cdotsc_{2, W}
\vdots
c_{H, 1}c_{H, 2}\cdotsc_{H, W}
出力
整数 X としてあり得るものが何通りあるかを、998244353 で割った余りを出力せよ。
入力例 1
2 2 1 31 41
出力例 1
5
例えば、以下の進行が考えられます。
- まず高橋君がマス (1, 2) にコマを置く。
- 高橋君がコマをマス (1, 2) からマス (1, 1) に動かす。その後、マス (1, 1) に書かれた数字 3 を黒板に書く。
- 青木君がコマをマス (1, 1) からマス (2, 1) に動かす。その後、マス (2, 1) に書かれた数字 4 を黒板に書く。
この場合、X = 34 となります。
他の例として、以下の進行も考えられます。
- まず高橋君がマス (2, 2) にコマを置く。
- 高橋君がコマをマス (2, 2) から動かさず、マス (2, 2) に書かれた数字 1 を黒板に書く。
- 青木君がコマをマス (2, 2) からマス (1, 2) に動かす。その後、マス (1, 2) に書かれた数字 1 を黒板に書く。
この場合、X = 11 となります。
X としてあり得る整数は、上記の例で示した 34, 11 の他にも 33, 44, 43 があります。また、それら以外の整数が X となることはありえません。
X としてあり得る整数の個数は 5 個であるので 5 を出力します。
入力例 2
2 3 4 777 777
出力例 2
1
整数 X としてあり得るのは、77777777 のみです。
入力例 3
10 10 300 3181534389 4347471911 4997373645 5984584273 1917179465 3644463294 1234548423 6826453721 5892467783 1211598363
出力例 3
685516949
998244353 で割った余りを出力することに注意して下さい。
Score : 600 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns, where each square contains a digit between 1 and 9. For each pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, the digit written on the square at the i-th row from the top and j-th column from the left is c_{i, j}.
Using this grid, Takahashi and Aoki will play together. First, Takahashi chooses a square and puts a piece on it. Then, the two will repeat the following procedures, 1. through 4., N times.
- Takahashi does one of the following two actions.
- Move the piece to another square that shares a row with the square the piece is on.
- Do nothing.
- Takahashi writes on a blackboard the digit written on the square the piece is on.
- Aoki does one of the following two actions.
- Move the piece to another square that shares a column with the square the piece is on.
- Do nothing.
- Aoki writes on the blackboard the digit written on the square the piece is on.
After that, there will be 2N digits written on the blackboard. Let d_1, d_2, \ldots, d_{2N} be those digits, in the order they are written. The two boys will concatenate the 2N digits in this order to make a 2N-digit integer X := d_1d_2\ldots d_{2N}.
Find the number, modulo 998244353, of different integers that X can become.
Constraints
- 2 \leq H, W \leq 10
- 1 \leq N \leq 300
- 1 \leq c_{i, j} \leq 9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W N
c_{1, 1}c_{1, 2}\cdotsc_{1, W}
c_{2, 1}c_{2, 2}\cdotsc_{2, W}
\vdots
c_{H, 1}c_{H, 2}\cdotsc_{H, W}
Output
Print the number, modulo 998244353, of different integers that X can become.
Sample Input 1
2 2 1 31 41
Sample Output 1
5
Below is one possible scenario.
- First, Takahashi puts the piece on (1, 2).
- Takahashi moves the piece from (1, 2) to (1, 1), and then writes the digit 3 written on (1, 1).
- Aoki moves the piece from (1, 1) to (2, 1), and then writes the digit 4 written on (2, 1).
In this case, we have X = 34.
Below is another possible scenario.
- First, Takahashi puts the piece on (2, 2).
- Takahashi keeps the piece on (2, 2), and then writes the digit 1 written on (2, 2).
- Aoki moves the piece from (2, 2) to (1, 2), and then writes the digit 1 written on (1, 2).
In this case, we have X = 11.
Other than these, X can also become 33, 44, or 43, but nothing else.
That is, there are five integers that X can become, so we print 5.
Sample Input 2
2 3 4 777 777
Sample Output 2
1
X can only become 77777777.
Sample Input 3
10 10 300 3181534389 4347471911 4997373645 5984584273 1917179465 3644463294 1234548423 6826453721 5892467783 1211598363
Sample Output 3
685516949
Be sure to find the count modulo 998244353.