AdditionalFile5583.zip

#5583. 「北大集训 2025」奇迹

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目背景

日复一日的机械运作着，面前三色荧光单调排列，四周充满黑暗的压抑。将来更是一眼到头的坏结局。

完全地虚无。“充实”的机械耕耘无法撬动贫瘠的思想土壤，尽管所思所念仍然在不断创造“奇迹”，且毫无意义。

我所希望的奇迹究竟是什么？我认为应该是一个小概率事件的产生，对若干部分造成了影响，这些部分又相互联系，进而获得了宏观上的巨变。

一月复一月，黑暗在逐渐侵蚀希望。在几乎必然的绝望之下，我也只能祈望奇迹的光亮再次来临。

题目描述

冬雀发现，许多看似毫无关联的事物之间，总会产生一些奇迹般的联系。

一个奇迹可以使用 $3 \times 3$ 的矩阵 $op$ 来表示，其中对于所有 $i, j \in \{0, 1, 2\}$，$op(i, j) \in \{0, 1, 2\}$。

对于 $0 \le i, j < 3^n$，设 $i, j$ 的三进制表示分别为 $\overline{(i_{n-1} \dots i_1 i_0)}_3$, $\overline{(j_{n-1} \dots j_1 j_0)}_3$（不足 $n$ 位的用前导 $0$ 补齐），定义 $i \oplus j = \overline{(k_{n-1} \dots k_1 k_0)}_3$，其中 $k_l = op(i_l, j_l)$ ($0 \le l < n$)。

若 $A, B, C$ 三个长度为 $3^n$ 的非负整数序列之间，蕴含一个奇迹 $op$，那么对于所有 $0 \le i < 3^n$，均有 $C_i = \left(\sum_{j \oplus k = i} A_j \times B_k\right) \bmod p$，其中 $p = 998,244,353$。

冬雀希望他能够找到一些奇迹，来解释这些看似毫无关联的事物之间的联系。

尽管这对于任意三个序列难以进行，但它仍然可以轻易的找到两个随机的序列 $A, B$，并通过一些神奇的操作，给出序列 $C$，使得 $A, B, C$ 三者内蕴含一个奇迹。

但是现在唯一的问题在于，它不知道奇迹是什么，所以它想让你找出一个可能的答案。

形式化地，给定三个长度为 $3^n$ 的非负整数序列，其中对于所有 $0 \le i < 3^n$，$A_i, B_i$ 均在在 $[0, p)$ 中独立均匀随机生成，且存在 $op$ 满足对于所有 $0 \le i < 3^n$，均有 $C_i = \left(\sum_{j \oplus k = i} A_j \times B_k\right) \bmod p$。你需要求出任意一个可能的 $op$。

输入格式

从标准输入读入数据。

本题包含多组测试数据。

输入的第一行包含一个正整数 $t$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$。
• 第二行包含 $3^n$ 个非负整数 $A_0, A_1, \dots, A_{3^n - 1}$。
• 第三行包含 $3^n$ 个非负整数 $B_0, B_1, \dots, B_{3^n - 1}$。
• 第四行包含 $3^n$ 个非负整数 $C_0, C_1, \dots, C_{3^n - 1}$。

输出格式

输出到标准输出。

对于每组测试数据，输出一行九个非负整数 $op(0,0), op(0,1), op(0,2), op(1,0), op(1,1), op(1,2), op(2,0), op(2,1), op(2,2)$，表示一个可能的 $op$。若有多个满足条件的 $op$，输出任意一个即可。

样例 1

输入

3
1
2 0 2
1 0 0
2 2 0
2
0 0 1 1 1 2 0 0 2
1 0 0 2 1 0 1 2 2
10 10 6 8 5 2 8 9 5
3
0 0 0 1 0 1 1 1 1 2 2 2 2 1 0 2 2 0 0 0 1 1 0 2 1 0 2
2 2 1 2 2 0 1 0 1 1 1 0 1 1 1 0 1 1 0 2 0 0 2 1 1 1 0
70 0 81 0 0 0 124 0 105 0 0 0 0 0 0 0 0 0 11 0 101 0 0 0 25 0 108

输出

1 2 0 0 0 0 0 0 0
1 1 1 0 2 0 0 1 2
0 2 2 0 0 0 2 2 2

子任务

对于所有测试数据，均有：

• $1 \le t \le 16$；
• $1 \le n \le 10$；
• 对于所有 $0 \le i < 3^n$，$A_i$ 均在 $[0, p)$ 中独立均匀随机生成；
• 对于所有 $0 \le i < 3^n$，$B_i$ 均在 $[0, p)$ 中独立均匀随机生成；
• 对于所有 $0 \le i < 3^n$，$0 \le C_i < p$；
• 存在至少一个 $op$ 满足条件。

特殊性质 A：存在 $x, y \in \{0,1,2\}$ 满足 $op = \begin{pmatrix} x & x & x \\ x & x & x \\ y & y & y \end{pmatrix}$。

特殊性质 B：存在 $x, y, z \in \{0,1,2\}$ 满足 $op = \begin{pmatrix} x & x & x \\ y & y & y \\ z & z & z \end{pmatrix}$。

特殊性质 C：存在 $x, y \in \{0,1,2\}$ 满足 $op = \begin{pmatrix} x & x & y \\ x & x & y \\ y & y & y \end{pmatrix}$。

特殊性质 D：存在 $a, b \in \{0,1,2\}$ 满足对于所有 $i, j \in \{0,1,2\}$，均有 $op(i,j) = (ai + bj) \bmod 3$；

特殊性质 E：对于所有 $i \in \{0,1,2\}$，均有 $op(i,0) = op(i,1)$。

特殊性质 F：对于所有 $i, j \in \{0,1,2\}$，均有 $op(i,j) \in \{0,1\}$。

提示

本题输入规模较大，请使用较为快速的输入方式。