问题陈述
在二维网格中,让 (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).
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 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