English · Original
Chinese · Translation
Formal · Original
A sequence _a_0, _a_1, ... is called a _recurrent binary sequence_, if each term _a__i_ (_i_ = 0, 1, ...) is equal to 0 or 1 and there exist coefficients such that
<center>_a__n_ = _c_1·_a__n_ - 1 + _c_2·_a__n_ - 2 + ... + _c__k_·_a__n_ - _k_ (_mod_ 2), </center>for all _n_ ≥ _k_. Assume that not all of _c__i_ are zeros.Note that such a sequence can be uniquely recovered from any _k_\-tuple {_a__s_, _a__s_ + 1, ..., _a__s_ + _k_ - 1} and so it is periodic. Moreover, if a _k_\-tuple contains only zeros, then the sequence contains only zeros, so this case is not very interesting. Otherwise the minimal period of the sequence is not greater than 2_k_ - 1, as _k_\-tuple determines next element, and there are 2_k_ - 1 non-zero _k_\-tuples. Let us call a sequence _long_ if its minimal period is exactly 2_k_ - 1. Your task is to find a long sequence for a given _k_, if there is any.
## Input
Input contains a single integer _k_ (2 ≤ _k_ ≤ 50).
## Output
If there is no long sequence for a given _k_, output "-1" (without quotes). Otherwise the first line of the output should contain _k_ integer numbers: _c_1, _c_2, ..., _c__k_ (coefficients). The second line should contain first _k_ elements of the sequence: _a_0, _a_1, ..., _a__k_ - 1. All of them (elements and coefficients) should be equal to 0 or 1, and at least one _c__i_ has to be equal to 1.
If there are several solutions, output any.
[samples]
## Note
1\. In the first sample: _c_1 = 1, _c_2 = 1, so _a__n_ = _a__n_ - 1 + _a__n_ - 2 (_mod_ 2). Thus the sequence will be:
<center></center>so its period equals 3 = 22 - 1.
2\. In the second sample: _c_1 = 0, _c_2 = 1, _c_3 = 1, so _a__n_ = _a__n_ - 2 + _a__n_ - 3 (_mod_ 2). Thus our sequence is:
<center></center>and its period equals 7 = 23 - 1.
Periods are colored.
一个序列 #cf_span[a0, a1, ...] 被称为 _递归二进制序列_，如果每一项 #cf_span[ai] #cf_span[(i = 0, 1, ...)] 都等于 0 或 1，并且存在系数使得
注意，这样的序列可以从任意一个 #cf_span[k]-元组 #cf_span[{as, as + 1, ..., as + k - 1}] 唯一恢复，因此它是周期性的。此外，如果一个 #cf_span[k]-元组全为零，则整个序列也全为零，这种情况并不有趣。否则，该序列的最小周期不超过 #cf_span[2k - 1]，因为一个 #cf_span[k]-元组决定下一个元素，而非零的 #cf_span[k]-元组共有 #cf_span[2k - 1] 个。我们称一个序列是 _长的_，如果它的最小周期恰好为 #cf_span[2k - 1]。你的任务是为给定的 #cf_span[k] 找到一个长序列（如果存在）。
输入包含一个整数 #cf_span[k] (#cf_span[2 ≤ k ≤ 50])。
如果对于给定的 #cf_span[k] 不存在长序列，则输出 "-1"（不含引号）。否则，输出的第一行应包含 #cf_span[k] 个整数：#cf_span[c1, c2, ..., ck]（系数）。第二行应包含序列的前 #cf_span[k] 个元素：#cf_span[a0, a1, ..., ak - 1]。它们（元素和系数）都必须为 0 或 1，且至少有一个 #cf_span[ci] 必须等于 1。
如果有多个解，输出任意一个即可。
1. 在第一个样例中：#cf_span[c1 = 1]，#cf_span[c2 = 1]，因此 #cf_span[an = an - 1 + an - 2 (mod 2)]。于是序列如下：
其周期等于 #cf_span[3 = 22 - 1]。
2. 在第二个样例中：#cf_span[c1 = 0]，#cf_span[c2 = 1]，#cf_span[c3 = 1]，因此 #cf_span[an = an - 2 + an - 3 (mod 2)]。于是我们的序列是：
其周期等于 #cf_span[7 = 23 - 1]。
周期已着色。
## Input
输入包含一个整数 #cf_span[k] (#cf_span[2 ≤ k ≤ 50])。
## Output
如果对于给定的 #cf_span[k] 不存在长序列，则输出 "-1"（不含引号）。否则，输出的第一行应包含 #cf_span[k] 个整数：#cf_span[c1, c2, ..., ck]（系数）。第二行应包含序列的前 #cf_span[k] 个元素：#cf_span[a0, a1, ..., ak - 1]。它们（元素和系数）都必须为 0 或 1，且至少有一个 #cf_span[ci] 必须等于 1。如果有多个解，输出任意一个即可。
[samples]
## Note
1. 在第一个样例中：#cf_span[c1 = 1]，#cf_span[c2 = 1]，因此 #cf_span[an = an - 1 + an - 2 (mod 2)]。于是序列如下：其周期等于 #cf_span[3 = 22 - 1]。
2. 在第二个样例中：#cf_span[c1 = 0]，#cf_span[c2 = 1]，#cf_span[c3 = 1]，因此 #cf_span[an = an - 2 + an - 3 (mod 2)]。于是我们的序列是：其周期等于 #cf_span[7 = 23 - 1]。
周期已着色。
Let $ k \in \mathbb{N} $ with $ 2 \leq k \leq 50 $.
A **recurrent binary sequence** $ (a_n)_{n=0}^\infty $, $ a_n \in \{0,1\} $, satisfies a linear recurrence of order $ k $:
$$
a_n = \sum_{i=1}^{k} c_i a_{n-i} \pmod{2}, \quad \text{for all } n \geq k,
$$
where $ c_i \in \{0,1\} $ are coefficients, not all zero.
The sequence is uniquely determined by its initial $ k $-tuple $ (a_0, a_1, \dots, a_{k-1}) \in \{0,1\}^k $.
The state space of consecutive $ k $-tuples has size $ 2^k $. Excluding the all-zero state (which leads to the zero sequence), there are $ 2^k - 1 $ non-zero states. The sequence is periodic, and its minimal period $ T $ satisfies $ T \leq 2^k - 1 $.
A sequence is called **long** if its minimal period is exactly $ 2^k - 1 $.
**Objective:**
Find coefficients $ (c_1, c_2, \dots, c_k) \in \{0,1\}^k $, not all zero, and an initial state $ (a_0, a_1, \dots, a_{k-1}) \in \{0,1\}^k $, not all zero, such that the resulting sequence has minimal period $ 2^k - 1 $.
If no such sequence exists, output "-1".
Otherwise, output:
- First line: $ c_1, c_2, \dots, c_k $
- Second line: $ a_0, a_1, \dots, a_{k-1} $
Note: Such a sequence exists if and only if the characteristic polynomial $ f(x) = x^k - \sum_{i=1}^k c_i x^{k-i} \in \mathbb{F}_2[x] $ is primitive. The initial state must be non-zero. A primitive polynomial of degree $ k $ over $ \mathbb{F}_2 $ exists for all $ k \geq 1 $, and guarantees a maximal period $ 2^k - 1 $ when paired with a non-zero initial state.
API Response (JSON)
{
"problem": {
"name": "E. Long sequence",
"description": {
"content": "A sequence _a_0, _a_1, ... is called a _recurrent binary sequence_, if each term _a__i_ (_i_ = 0, 1, ...) is equal to 0 or 1 and there exist coefficients such that <center>_a__n_ = _c_1·_a__n_ - 1 + ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF86E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "A sequence _a_0, _a_1, ... is called a _recurrent binary sequence_, if each term _a__i_ (_i_ = 0, 1, ...) is equal to 0 or 1 and there exist coefficients such that\n\n<center>_a__n_ = _c_1·_a__n_ - 1 + ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "一个序列 #cf_span[a0, a1, ...] 被称为 _递归二进制序列_，如果每一项 #cf_span[ai] #cf_span[(i = 0, 1, ...)] 都等于 0 或 1，并且存在系数使得\n\n注意，这样的序列可以从任意一个 #cf_span[k]-元组 #cf_span[{as, as + 1, ..., as + k - 1}] 唯一恢复，因此它是周期性的。此外，如果一个 #...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ k \\in \\mathbb{N} $ with $ 2 \\leq k \\leq 50 $.\n\nA **recurrent binary sequence** $ (a_n)_{n=0}^\\infty $, $ a_n \\in \\{0,1\\} $, satisfies a linear recurrence of order $ k $:\n\n$$\na_n = \\sum_{i=1}^{k}...",
"is_translate": false,
"language": "Formal"
}
]
}