CF86E Long sequence

一个序列 $a_0, a_1, \ldots$ 被称为循环二进制序列，当且仅当每项 $a_i$（$i = 0, 1, \ldots$）都是 0 或 1，并且存在系数 $c_1, c_2, \ldots, c_k$，使得对所有的 $n \ge k$，都有 $$ a_n = c_1 \times a_{n-1} + c_2 \times a_{n-2} + \cdots + c_k \times a_{n-k} \ (\text{mod}\ 2) $$ 成立。假设这些系数 $c_i$ 中至少有一个不为零。这样的序列可以通过任意一个 $k$ 元组 $\{a_s, a_{s+1}, \ldots, a_{s+k-1}\}$ 唯一决定，因此它是有周期性的。此外，如果一个 $k$ 元组全是零，则整个序列也全为零，这种情形没有任何研究价值。否则，序列的最小周期不超过 $2^k - 1$，因为每个 $k$ 元组决定下一个元素，而非零 $k$ 元组的个数为 $2^k - 1$。我们将一个周期恰好为 $2^k - 1$ 的序列称为长周期序列。你的任务是，给定 $k$ 后，找出一个长周期序列（如果存在）。

输入包括一个整数 $k$（$2 \le k \le 50$）。

如果给定的 $k$ 下不存在长周期序列，则输出 `-1`（不加引号）。否则，输出分两行： - 第一行包含 $k$ 个整数：$c_1, c_2, \ldots, c_k$（系数）， - 第二行包含序列的前 $k$ 个元素：$a_0, a_1, \ldots, a_{k-1}$。 这些元素和系数均为 0 或 1，并且至少有一个 $c_i$ 为 1。 如果有多种可能的解，可以输出任意一个。

1. 在第一个示例中：$c_1 = 1$，$c_2 = 1$，所以 $a_n = a_{n-1} + a_{n-2} \ (\text{mod}\ 2)$。因此序列为：  其周期为 $3 = 2^2 - 1$。 2. 在第二个示例中：$c_1 = 0$，$c_2 = 1$，$c_3 = 1$，所以 $a_n = a_{n-2} + a_{n-3} \ (\text{mod}\ 2)$。因此序列为：  其周期为 $7 = 2^3 - 1$。 示例中的周期部分已用颜色标出。 **本翻译由 AI 自动生成**