AT_ahc032_a [AHC032A] Mod Stamp
题目描述
在一个二维格子中，最左上角的格子的坐标为 $(0, 0)$，从这里向下走 $i$ 格、向右走 $j$ 格后的位置坐标为 $(i, j)$。
有一个 $N \times N$ 的棋盘。最初，棋盘上每个格子 $(i, j)$ 都被赋予了一个整数 $a_{i, j}$。
有 $M$ 个 $3 \times 3$ 的“印章”。对于第 $m$ 个印章（$0 \leq m \leq M - 1$），其每个格子 $(i, j)$ 上都写有一个整数 $s_{m, i, j}$。
你最多可以进行 $K$ 次如下操作：
- 选择一个印章 $m$ 和棋盘上的一个格子 $(p, q)$（$0 \leq p, q \leq N - 3$），将印章 $m$ 的坐标 $(0, 0)$ 与棋盘的格子 $(p, q)$ 对齐并盖章。此操作会使得对于印章的每个格子 $(i, j)$（$0 \leq i, j \leq 2$），棋盘上对应的格子 $(p + i, q + j)$ 的值增加 $s_{m, i, j}$。不能将印章盖出棋盘边界，也不能旋转印章。
同一个印章可以使用多次，也可以有印章一次都不使用。同一个位置可以盖多次印章。
请最大化最终棋盘上所有格子的值对 $998244353$ 取余后的总和。
输入格式
输入通过标准输入按以下格式给出。
> $N$ $M$ $K$
> $a_{0, 0}$ $\cdots$ $a_{0, N - 1}$
> $\vdots$
> $a_{N - 1, 0}$ $\cdots$ $a_{N - 1, N - 1}$
> $s_{0, 0, 0}$ $s_{0, 0, 1}$ $s_{0, 0, 2}$ $s_{0, 1, 0}$ $s_{0, 1, 1}$ $s_{0, 1, 2}$ $s_{0, 2, 0}$ $s_{0, 2, 1}$ $s_{0, 2, 2}$
> $\vdots$
> $s_{M - 1, 0, 0}$ $s_{M - 1, 0, 1}$ $s_{M - 1, 0, 2}$ $s_{M - 1, 1, 0}$ $s_{M - 1, 1, 1}$ $s_{M - 1, 1, 2}$ $s_{M - 1, 2, 0}$ $s_{M - 1, 2, 1}$ $s_{M - 1, 2, 2}$
各个数值满足以下约束：
- $N = 9$
- $M = 20$
- $K = 81$
- $0 \leq a_{i, j} \leq 998244352$
- $0 \leq s_{m, i, j} \leq 998244352$
输出格式
输出盖章的次数 $L$（$0 \leq L \leq K$），以及每次操作选择的印章编号和棋盘格子的位置。对于第 $l$ 次操作，选择的印章和棋盘格子分别为 $m_l$（$0 \leq m_l \leq M - 1$）、$(p_l, q_l)$（$0 \leq p_l, q_l \leq N - 3$）。输出格式如下：
> $L$
> $m_0$ $p_0$ $q_0$
> $m_1$ $p_1$ $q_1$
> $\vdots$
> $m_{L - 1}$ $p_{L - 1}$ $q_{L - 1}$
说明/提示
### 得分
所有操作结束后，棋盘上格子 $(i, j)$ 的最终值记为 $b_{i, j}$，则得分为：
\[
\sum_{i = 0}^{N - 1}{\sum_{j = 0}^{N - 1}{(b_{i, j} \bmod 998244353)}}
\]
其中，$b_{i, j} \bmod 998244353$ 表示 $b_{i, j}$ 除以 $998244353$ 的余数。
如果操作次数超过 $K$ 或输出了非法操作，则判定为 WA。
共有 150 个测试用例，所有测试用例得分之和为本次提交的得分。如果有一个或多个测试用例输出非法或超时，则本次提交整体判定为 WA 或 TLE。比赛期间以获得的最高分决定最终排名，比赛结束后不再进行系统测试。如果有多名参赛者得分相同，则排名相同，与提交时间无关。
### 输入生成方法
用 $\mathrm{rand}(L, U)$ 表示在 $L$ 到 $U$ 之间均匀随机生成的整数。
每个 $a_{i, j}$ 和 $s_{m, i, j}$ 都独立生成，$a_{i, j} = \mathrm{rand}(0, 998244352)$，$s_{m, i, j} = \mathrm{rand}(0, 998244352)$。
### 工具（输入生成器与可视化工具）
- [网页版](https://img.atcoder.jp/ahc032/e2weanqa.html?lang=ja)：功能更强大，可动画显示。
- [本地版](https://img.atcoder.jp/ahc032/e2weanqa.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。
- [Windows 版编译好的二进制文件](https://img.atcoder.jp/ahc032/e2weanqa_windows.zip)：如不方便配置 Rust 环境可使用此版本。
比赛期间禁止分享可视化结果、讨论解法或思路。请注意遵守规则。
由 ChatGPT 4.1 翻译