AT_abc228_g [ABC228G] Digits on Grid

题目描述

有一个纵向 $H$ 行、横向 $W$ 列的网格，每个格子里写有 $1$ 到 $9$ 之间的某个数字。对于满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$，第 $i$ 行第 $j$ 列的格子中写的数字为 $c_{i, j}$。

高桥君和青木君用这个网格进行两人游戏。首先，高桥君选择任意一个格子，并在该格子上放置棋子。之后，两人按照以下步骤 1 到 4，重复 $N$ 次：

1. 高桥君可以选择以下两种操作之一：
   • 将棋子移动到同一行的另一个格子。
   • 什么也不做。
2. 高桥君将当前棋子所在格子的数字写在黑板上。
3. 青木君可以选择以下两种操作之一：
   • 将棋子移动到同一列的另一个格子。
   • 什么也不做。
4. 青木君将当前棋子所在格子的数字写在黑板上。

经过上述过程后，黑板上会依次写下 $2N$ 个数字。将这些数字按写入顺序依次排列，记为 $d_1, d_2, \ldots, d_{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$ 取模后的结果。

输入输出样例 #1

输入 #1

2 2 1
31
41

输出 #1

5

输入输出样例 #2

输入 #2

2 3 4
777
777

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

685516949

说明/提示

限制条件

• $2 \leq H, W \leq 10$
• $1 \leq N \leq 300$
• $1 \leq c_{i, j} \leq 9$
• 所有输入均为整数

样例解释 1

例如，以下流程是可能的：

• 首先高桥君将棋子放在格子 $(1, 2)$。
• 高桥君将棋子从 $(1, 2)$ 移动到 $(1, 1)$，然后将格子 $(1, 1)$ 上的数字 $3$ 写在黑板上。
• 青木君将棋子从 $(1, 1)$ 移动到 $(2, 1)$，然后将格子 $(2, 1)$ 上的数字 $4$ 写在黑板上。 此时，$X = 34$。

另一个例子如下：

• 首先高桥君将棋子放在格子 $(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

唯一可能的 $X$ 是 $77777777$。

样例解释 3

请注意要对 $998244353$ 取模后输出。

由 ChatGPT 4.1 翻译