AT_ahc032_a [AHC032A] Mod Stamp

[problemUrl]: https://atcoder.jp/contests/ahc032/tasks/ahc032_a 二次元のマス目における一番左上のマスの座標を $ (0,\ 0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,\ j) $ とする。 $ N\ \times\ N $ マスの盤面がある。最初、盤面の各マス $ (i,\ j) $ に整数 $ a_{i,\ j} $ が設定されている。 $ 3\ \times\ 3 $ マスのスタンプが $ M $ 個ある。スタンプ $ 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} $ [例を見る](https://img.atcoder.jp/ahc032/e2weanqa.html?lang=ja&seed=0&output=sample)

### 得点 全ての操作を終えた後、盤面のマス $ (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 となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数を $ \mathrm{rand}(L,\ U) $ と表す。 各 $ a_{i,\ j} $ と $ s_{m,\ i,\ j} $ は全て独立に、 $ a_{i,\ j}\ =\ \mathrm{rand}(0,\ 998244352) $, $ s_{m,\ i,\ j}\ =\ \mathrm{rand}(0,\ 998244352) $ により生成する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](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言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。