{"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 + _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.\n\n## Input\n\nInput contains a single integer _k_ (2 ≤ _k_ ≤ 50).\n\n## Output\n\nIf 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.\n\nIf there are several solutions, output any.\n\n[samples]\n\n## Note\n\n1\\. 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:\n\n<center>![image](https://espresso.codeforces.com/9e607bb053ab75d930dbe37f56aad04291e5b61e.png)</center>so its period equals 3 = 22 - 1.\n\n2\\. 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:\n\n<center>![image](https://espresso.codeforces.com/9358c328cb7a8b393aa2c72d363198b6b799839e.png)</center>and its period equals 7 = 23 - 1.\n\nPeriods are colored.","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}] 唯一恢复，因此它是周期性的。此外，如果一个 #cf_span[k]-元组全为零，则整个序列也全为零，这种情况并不有趣。否则，该序列的最小周期不超过 #cf_span[2k - 1]，因为一个 #cf_span[k]-元组决定下一个元素，而非零的 #cf_span[k]-元组共有 #cf_span[2k - 1] 个。我们称一个序列是 _长的_，如果它的最小周期恰好为 #cf_span[2k - 1]。你的任务是为给定的 #cf_span[k] 找到一个长序列（如果存在）。\n\n输入包含一个整数 #cf_span[k] (#cf_span[2 ≤ k ≤ 50])。\n\n如果对于给定的 #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。\n\n如果有多个解，输出任意一个即可。\n\n1. 在第一个样例中：#cf_span[c1 = 1]，#cf_span[c2 = 1]，因此 #cf_span[an = an - 1 + an - 2  (mod 2)]。于是序列如下：\n\n其周期等于 #cf_span[3 = 22 - 1]。\n\n2. 在第二个样例中：#cf_span[c1 = 0]，#cf_span[c2 = 1]，#cf_span[c3 = 1]，因此 #cf_span[an = an - 2 + an - 3  (mod 2)]。于是我们的序列是：\n\n其周期等于 #cf_span[7 = 23 - 1]。\n\n周期已着色。\n\n## Input\n\n输入包含一个整数 #cf_span[k] (#cf_span[2 ≤ k ≤ 50])。\n\n## Output\n\n如果对于给定的 #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。如果有多个解，输出任意一个即可。\n\n[samples]\n\n## Note\n\n1. 在第一个样例中：#cf_span[c1 = 1]，#cf_span[c2 = 1]，因此 #cf_span[an = an - 1 + an - 2  (mod 2)]。于是序列如下：其周期等于 #cf_span[3 = 22 - 1]。\n2. 在第二个样例中：#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]。\n周期已着色。","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} c_i a_{n-i} \\pmod{2}, \\quad \\text{for all } n \\geq k,\n$$\n\nwhere $ c_i \\in \\{0,1\\} $ are coefficients, not all zero.\n\nThe sequence is uniquely determined by its initial $ k $-tuple $ (a_0, a_1, \\dots, a_{k-1}) \\in \\{0,1\\}^k $.\n\nThe 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 $.\n\nA sequence is called **long** if its minimal period is exactly $ 2^k - 1 $.\n\n**Objective:**  \nFind 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 $.\n\nIf no such sequence exists, output \"-1\".\n\nOtherwise, output:\n- First line: $ c_1, c_2, \\dots, c_k $\n- Second line: $ a_0, a_1, \\dots, a_{k-1} $\n\nNote: 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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF86E","tags":["brute force","math","matrices"],"sample_group":[["2","1 1\n1 0"],["3","0 1 1\n1 1 1"]],"created_at":"2026-03-03 11:00:39"}}