Digits on Grid

题目描述

有一个由 $H$ 行横向行和 $W$ 列纵向列组成的网格，每个格子里包含一个介于 $1$ 到 $9$ 之间的数字。 对于每一对整数 $(i, j)$，满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$，位于从上数第 $i$ 行、从左数第 $j$ 列的格子上写着的数字为 $c_{i, j}$。 利用这个网格，高桥（Takahashi）和青木（Aoki）将一起进行游戏。 首先，高桥选择一个格子并将一个棋子放在该格子上。 然后，两人将重复以下步骤 1. 到 4.，共 $N$ 次。

高桥执行以下两种操作之一。 将棋子移动到与棋子所在格子共享同一行的另一个格子。 什么也不做。

高桥把棋子所在格子上写着的数字写到黑板上。 青木执行以下两种操作之一。 将棋子移动到与棋子所在格子共享同一列的另一个格子。 什么也不做。

青木把棋子所在格子上写着的数字写到黑板上。

之后，黑板上将写下 $2N$ 个数字。令 $d_1, d_2, \ldots, d_{2N}$ 为按写下顺序得到的这些数字。 两位男孩将按此顺序将这 $2N$ 个数字连接起来形成一个 $2N$ 位的整数 $X := d_1d_2\ldots d_{2N}$。 求不同的整数 $X$ 可以成为多少个，对结果取模 $998244353$。

输入格式

输入由标准输入按以下格式提供： $H$ $W$ $N$ $c_{1, 1}$$c_{1, 2}$$\cdots$$c_{1, W}$ $c_{2, 1}$$c_{2, 2}$$\cdots$$c_{2, W}$ \vdots $c_{H, 1}$$c_{H, 2}$$\cdots$$c_{H, W}$

输出格式

输出不同的整数 $X$ 可以成为的个数，对 $998244353$ 取模后的结果。

2 2 1
31
41

5

2 3 4
777
777

1

10 10 300
3181534389
4347471911
4997373645
5984584273
1917179465
3644463294
1234548423
6826453721
5892467783
1211598363

685516949

提示

$2 \leq H, W \leq 10$ $1 \leq N \leq 300$ $1 \leq c_{i, j} \leq 9$ 输入中的所有数值均为整数。下面是一个可能的情形。

首先，高桥把棋子放在 $(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$ 还可以成为 $33$、$44$ 或 $43$，但没有其他可能。
也就是说，有五个整数 $X$ 可以成为，所以我们输出 $5$.
$X$ 只能成为 $77777777$.
请注意对 $998244353$ 取模。

标签: AtCoder|abc228G

来源

AtCoder|abc228G