AT_ahc032_a.[AHC032A] Mod Stamp

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一个二维格子中，最左上角的格子的坐标为 $(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}$

输入输出样例

输入#1

9 20 81
24323530 980293589 859258684 185499104 894688371 236405725 111530575 250271104 495624658
769596495 264300425 88876278 146578260 565437828 737999180 725732147 57726456 323844609
40096771 928203404 501627737 804865949 814572382 849529199 189832922 910184599 467494517
962420139 432607222 59818053 858072870 914485919 446805915 138548911 345246064 245004268
477044564 12166358 931360092 799278793 865992483 339109407 614502753 736626962 801948371
281576446 640350568 771040910 823574138 350308411 930294372 585808288 700370699 426021090
289960346 566527193 119082954 148354804 902944838 516738876 930961873 812731496 172242940
921564237 662077279 49476329 593121834 377147282 862136854 791213996 686329230 7403815
501340655 979965930 839183331 303883398 490179686 492481098 160122974 114672637 82049594
975741402 918762324 476374754
906657349 359110092 978536040
84599745 368692094 744129488
261705356 216870728 556481274
317767465 457532475 532110106
125703669 839188333 425571806
291667039 37052662 1276219
305291998 653050074 220563016
332525785 400712871 520185762
393148157 178758620 933441647
205044518 579917402 498932315
411369672 664953833 274696537
654712800 802006144 682742340
864455037 533661060 207561332
605472509 577911453 942938903
576270626 688256275 33493069
481710779 902547317 817131623
291465541 863597953 772086608
417987422 136453150 615090472
760882895 841541285 914039365
359505208 780663578 774735965
188919347 431579412 464452916
854985721 70294202 663019966
157776983 3557297 439447307
621014939 759908222 932643321
184225959 884108948 693640679
361651737 846036661 975413204
479224933 700946167 622558051
495003914 325785117 513339213
70238660 857642866 297571112
374937799 48000646 849682071
528095305 232520890 469018467
952599070 610262715 232403912
316958602 24859140 385411996
304561106 853230688 859071983
266806117 99442261 881952734
708824083 752081152 915353520
261135036 48934653 945657700
255395109 742827901 445178710
906120195 565840603 316740986
736297599 447489530 680619574
654670835 694926131 897183420
958993686 813942152 196144122
324334792 928014325 852381591
194958307 642660824 128931372
303306950 687790222 930130148
591510740 614681348 113389792
160195595 683240268 555351204
218729338 196609467 724290289
47413572 552092134 337674489
410209863 549012244 186533965
452647000 449090484 733453206
106059177 888943736 940915649
692940521 382797569 893532614
52383100 783583840 634565824
168433778 751831139 356971915
870682287 872212766 75893565
262231629 844472478 843213274
499286296 502562654 725538734
467780532 720085509 907848638

输出#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)$ 。

工具（输入生成器与可视化工具）

网页版：功能更强大，可动画显示。
本地版：需安装 Rust 语言编译环境。
- Windows 版编译好的二进制文件：如不方便配置 Rust 环境可使用此版本。

比赛期间禁止分享可视化结果、讨论解法或思路。请注意遵守规则。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页