C. 矩阵快速幂

题目描述

给定一个大小为 $2^n\times m$ 的循环矩阵 $A$ （即第一行和最后一行相邻，第一列和最后一列相邻）。 定义一次操作是将所有位置同时变为其自己和周围的格子的异或和。 即新的矩阵 $A^\prime$ 满足： $A^\prime_{i,j}=A_{i,j }\oplus A_{i,j-1}\oplus A_{i,j+1}\oplus A_{i+1,j}\oplus A_{i−1,j}$。 现在给定矩阵 $X$，请找到唯一的矩阵 $A$ 使得 $A$ 操作 $K$ 次是 $X$，如果无解或有不少于 $2$ 个矩阵 满足条件，输出 $-1$。

输入格式

第一行给定 $n,m,K$ 三个数。

接下来的 $2^n$ 行分别有 $m$ 个数，表示矩阵 $X$。

输出格式

若有唯一矩阵 $A$，输出矩阵 $A$，若有多种解或无解，输出 $-1$。

样例 #1

样例输入 #1

1 2 1
0 1
1 1

样例输出 #1

0 1
1 1

样例 #2

样例输入 #2

4 10 8
68583 774950 499057 645374 481559 695891 118026 932912 925666 348853 
980734 240652 85350 309112 63605 838435 915560 777212 23104 434065 
142534 274596 821266 579514 687980 546929 367415 160314 871142 344348 
170333 458225 637797 187889 622098 637855 883780 258623 570767 327944 
607477 69999 87095 211326 897611 150700 568261 813170 927913 591365 
247235 70446 384460 587000 168459 72439 652429 535874 751254 523570 
398722 440086 500294 555018 146474 122392 192873 548754 899515 282139 
876698 25490 870638 963794 236817 768249 114493 323577 99917 560905 
914942 865652 149850 817901 452652 318310 890341 105080 372683 160093 
147149 771405 118678 165943 844923 265152 806835 37795 813906 706349 
838434 209103 731840 709071 172896 487156 995819 805889 810733 95736 
885294 244173 479887 35143 62073 932539 353453 470913 556118 726137 
149505 221767 16040 268183 387710 860963 533336 194544 417257 865741 
419392 255690 74843 151231 483261 766239 156886 997579 90627 486118 
611814 975921 730291 91701 11063 310864 542739 883017 781777 98857 
127652 931283 320624 143692 717965 708334 523155 769800 421377 940412

样例输出 #2

499706 1012037 544665 177787 544018 270272 482204 800744 973700 398360 
259811 310483 847694 652053 939211 653502 148464 835720 126803 975818 
903325 924399 285123 1041564 334156 600521 737251 955684 769432 380631 
432907 832593 815790 274118 217792 673638 417404 512575 553208 943974 
810363 996785 513883 415497 712215 678854 47879 933987 184021 553943 
566085 533659 483287 468104 663902 521451 1043586 117396 801105 922429 
448705 997020 584340 289155 626707 206613 214701 430222 534487 911369 
1000118 996498 881054 185378 1014726 218210 104265 669881 1004466 885538 
428087 554090 684916 1020360 963097 761679 141633 54753 69309 708822 
169221 1006894 125815 580793 176612 330144 1031912 646873 82111 804058 
88489 528954 542150 518198 145071 338883 577545 371969 382797 838339 
529658 699639 674420 832191 330753 431887 1029132 270091 1039520 370565 
1016103 833172 933913 775594 130966 226473 677361 360992 231743 262521 
220459 487198 139918 662674 23550 998707 337613 954558 465381 955718 
79554 467752 557425 892245 168704 776264 670022 195405 57941 285260 
851386 1000501 356834 513848 878632 696897 191815 506775 556796 435934

数据范围

对于所有数据，保证 $0\leq n\leq 10,1\leq m\leq 2^{10},1\leq K,X_{i,j}\leq 10^6$。

• Subtask 1（1 pts）：$n,k\leq 1,m\leq 2$。
• Subtask 2（3 pts）：$n\leq 2,m\leq 4,k\leq 10$。
• Subtask 3（12 pts）：$n\leq 4,m\leq 16,k\leq 10$。
• Subtask 4（24 pts）：$m=2^n$。
• Subtask 5（60 pts）：无特殊限制。