← 返回题目列表

AtCoder · ahc032_a

A. 模组印章

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

问题陈述

在二维网格中,让 (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),一个整数 s_{m,i,j} 每个方格都写着 (i, j).

您最多可以执行以下操作 K 次。

  • 选择图章 m 和一个正方形 (p, q) (0 \leq p, q \leq N - 3) 在板上。按下图章,使其坐标 (0, 0) 与正方形对齐 (p, q) 在板上。 该操作增加了平方的值 (p + i, q + j) 在板上 每个方格的 s_{m,i,j} 邮票上有 (i, j) (0 \leq i, j \leq 2) 。 您不能将印章压到板的边界之外,也不能旋转印章。

您可以多次使用同一个印章,或者拥有根本未使用过的印章。在同一个方块上多次盖章也是可以接受的。

请将最终棋盘上每个方格的值除以所得的余数之和最大化 998244353.

评分

执行完所有操作后,让 b_{i, j} 是分配给平方的整数 (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} by 998244353.

如果操作次数超过 K 或者如果输出非法操作,提交将被判断为 WA.

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出:

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) 是操作次数,并且 m_l (0 \leq m_l \leq M - 1) 和 (p_l, q_l) (0 \leq p_l, q_l \leq N - 3) 是在 分别是 l第次操作。然后,按以下格式输出到标准输出:

L
m_0 p_0 q_0
m_1 p_1 q_1
\vdots
m_{L - 1} p_{L - 1} q_{L - 1}

显示示例

输入生成

让 \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).

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。


示例输入 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

4
0 1 6
6 6 6
18 6 1
16 1 5