CF1713F Lost Array

我的 orzlers，我们可以把这个问题从 $O(S^3)$ 优化到 $O\left(T^\frac{5}{9}\right)$！ —— Orzlim 教创始人 Spyofgame 很久以前，Spyofgame 发明了著名的数组 $a$（$1$ 下标）长度为 $n$，其中包含了关于世界和生命的信息。之后，他决定将其转换为矩阵 $b$（$0$ 下标），大小为 $(n+1) \times (n+1)$，其中包含了关于世界、生命以及更深层次的信息。 Spyofgame 按照以下规则将 $a$ 转换为 $b$： - 当 $0 \leq i \leq n$ 时，$b_{i,0} = 0$； - 当 $1 \leq i \leq n$ 时，$b_{0,i} = a_i$； - 当 $1 \leq i, j \leq n$ 时，$b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}$。 这里 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 今天，考古学家发现了著名的矩阵 $b$。然而，矩阵中的许多元素已经遗失。他们只知道 $b_{i,n}$ 的值，其中 $1 \leq i \leq n$（注意这些是最后一列的部分元素，而不是最后一行）。 考古学家想知道，是否存在一个可能的数组 $a$。你能帮他们还原出任意一个可能的 $a$ 吗？

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）。 第二行包含 $n$ 个整数 $b_{1,n}, b_{2,n}, \ldots, b_{n,n}$（$0 \leq b_{i,n} < 2^{30}$）。

如果存在某个数组 $a$ 与已知信息一致，输出一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$。如果有多个解，输出任意一个即可。 如果不存在这样的数组，输出 $-1$。

如果我们令 $a = [1,2,3]$，那么 $b$ 如下： | $\bf{0}$ | $\bf{1}$ | $\bf{2}$ | $\bf{3}$ | |:-:|:-:|:-:|:-:| | $\bf{0}$ | $1$ | $3$|$0$ | | $\bf{0}$ | $1$ | $2$ | $2$ | | $\bf{0}$ | $1$ |$3$ | $1$ | 生成的 $b_{1,n}, b_{2,n}, \ldots, b_{n,n}$ 为 $[0,2,1]$，这与考古学家发现的结果一致。 由 ChatGPT 4.1 翻译