← 返回题目列表

Codeforces · 86/E

E. 长序列

中文机器翻译题面 查看原题

序列 a0, a1, ... 称为循环二元序列,如果每个项 ai (i = 0, 1, ...) 等于 0 或 1 并且存在系数 $$c_1, c_2, \ldots, c_k \in \{0, 1\}$$ 使得

an = c1·an - 1 + c2·an - 2 + ... + ck·an - k (mod 2),

请注意,这样的序列可以从任何 k 元组 {as, as + 1, ..., as + k - 1} 中唯一恢复,因此它是周期性的。此外,如果 k 元组仅包含零,则序列也仅包含零,因此这种情况不是很有趣。否则序列的最小周期不大于2k - 1,因为k元组决定下一个元素,并且有2k - 1个非零k元组。如果一个序列的最小周期正好是 2k - 1,我们称该序列为长序列。您的任务是针对给定 k(如果存在)找到一个长序列。

输入

输入包含单个整数 k (2 ≤ k ≤ 50)。

输出

如果给定的 k 没有长序列,则输出“-1”(不带引号)。否则,输出的第一行应包含 k 个整数:c1、c2、...、ck(系数)。第二行应包含序列的前 k 个元素:a0, a1, ..., ak - 1。所有这些(元素和系数)应等于 0 或 1,并且至少有一个 ci 必须等于 1。

如果有多个解,则输出任意一个。

示例

输入 #1

2

输出 #1

1 1
1 0

输入 #2

3

输出 #2

0 1 1
1 1 1

注意

1. 在第一个示例中:c1 = 1,c2 = 1,因此 an = an - 1 + an - 2 (mod 2)。因此顺序将是:

因此其周期等于 3 = 22 - 1。

2. 在第二个示例中:c1 = 0、c2 = 1、c3 = 1,因此 an = an - 2 + an - 3 (mod 2)。因此我们的顺序是:

其周期等于 7 = 23 - 1。

句点是彩色的。