← 返回题目列表

AtCoder · abc228_g

G. 网格上的数字

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个网格 H 水平行和 W 垂直列,其中每个方格包含一个数字 1 和 9。 对于每对整数 (i, j) 这样 1 \leq i \leq H 和 1 \leq j \leq W,写在方块上的数字 i从顶部数第行和 j左起第 列是 c_{i, j}.

使用这个网格,高桥和青木将一起玩。 首先,高桥选择一个正方形,并在上面放一块棋子。 然后,两人将重复以下过程,1.到4., N 次。

  1. Takahashi 执行以下两个操作之一。
    • 将棋子移动到另一个方格, 共享一行 与该块所在的正方形。
    • 什么都不做。
  2. 高桥在黑板上写下棋子所在方块上写的数字。
  3. Aoki 执行以下两个操作之一。
    • 将棋子移动到另一个方格, 分享专栏 与该块所在的正方形。
    • 什么都不做。
  4. 青木在黑板上写下棋子所在方块上写的数字。

之后,将会有 2N 数字写在黑板上。让 d_1, d_2, \ldots, d_{2N} 是那些数字,按照它们的书写顺序排列。 这两个男孩将串联起来 2N 数字按此顺序进行 2N- 数字整数 X := d_1d_2\ldots d_{2N}.

求模数 998244353,不同的整数 X 可以成为。

约束

  • 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}

输出

打印数字,模数 998244353,不同的整数 X 可以成为。


示例输入 1

2 2 1
31
41

示例输出 1

5

以下是一种可能的情况。

  • 首先,高桥把这件作品穿上 (1, 2).
  • 高桥将棋子从 (1, 2) to (1, 1),然后写入数字 3 写于 (1, 1).
  • 青木将棋子从 (1, 1) to (2, 1),然后写入数字 4 写于 (2, 1).

在这种情况下,我们有 X = 34.
下面是另一种可能的情况。

  • 首先,高桥把这件作品穿上 (2, 2).
  • 高桥继续演奏 (2, 2),然后写入数字 1 写于 (2, 2).
  • 青木将棋子从 (2, 2) to (1, 2),然后写入数字 1 写于 (1, 2).

在这种情况下,我们有 X = 11。 除了这些之外, X 也可以变成 33, 44,或 43,但仅此而已。
也就是说,有五个整数 X 可以变成,所以我们打印 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.