English · Original
Chinese · Translation
Formal · Original
Suppose you have two polynomials and . Then polynomial can be uniquely represented in the following way:
This can be done using [long division](https://en.wikipedia.org/wiki/Polynomial_long_division). Here, denotes the degree of polynomial _P_(_x_). is called the remainder of division of polynomial by polynomial , it is also denoted as .
Since there is a way to divide polynomials with remainder, we can define Euclid's algorithm of finding the greatest common divisor of two polynomials. The algorithm takes two polynomials . If the polynomial is zero, the result is , otherwise the result is the value the algorithm returns for pair . On each step the degree of the second argument decreases, so the algorithm works in finite number of steps. But how large that number could be? You are to answer this question.
You are given an integer _n_. You have to build two polynomials with degrees not greater than _n_, such that their coefficients are integers not exceeding 1 by their absolute value, the leading coefficients (ones with the greatest power of _x_) are equal to one, and the described Euclid's algorithm performs exactly _n_ steps finding their greatest common divisor. Moreover, the degree of the first polynomial should be greater than the degree of the second. By a step of the algorithm we mean the transition from pair to pair .
## Input
You are given a single integer _n_ (1 ≤ _n_ ≤ 150) — the number of steps of the algorithm you need to reach.
## Output
Print two polynomials in the following format.
In the first line print a single integer _m_ (0 ≤ _m_ ≤ _n_) — the degree of the polynomial.
In the second line print _m_ + 1 integers between - 1 and 1 — the coefficients of the polynomial, from constant to leading.
The degree of the first polynomial should be greater than the degree of the second polynomial, the leading coefficients should be equal to 1. Euclid's algorithm should perform exactly _n_ steps when called using these polynomials.
If there is no answer for the given _n_, print _\-1_.
If there are multiple answer, print any of them.
[samples]
## Note
In the second example you can print polynomials _x_2 - 1 and _x_. The sequence of transitions is
<center>(_x_2 - 1, _x_) → (_x_, - 1) → ( - 1, 0).</center>There are two steps in it.
假设你有两个多项式 $P(x)$ 和 $Q(x)$。那么多项式 $P(x)$ 可以唯一地表示为如下形式：
$$
P(x) = Q(x) \cdot D(x) + R(x)
$$
这可以通过长除法完成。这里，$\deg(P(x))$ 表示多项式 $P(x)$ 的次数。$R(x)$ 称为 $P(x)$ 除以 $Q(x)$ 的余数，也记作 $P(x) \bmod Q(x)$。
由于存在带余除法，我们可以定义求两个多项式最大公因式的欧几里得算法。该算法接收两个多项式 $(P(x), Q(x))$。若多项式 $Q(x)$ 为零，则结果为 $P(x)$；否则，结果为算法对数对 $(Q(x), P(x) \bmod Q(x))$ 返回的值。在每一步中，第二个参数的次数都会减少，因此算法在有限步内终止。但这个步数最多能有多大？你需要回答这个问题。
给你一个整数 $n$。你需要构造两个多项式，它们的次数都不超过 $n$，系数为绝对值不超过 $1$ 的整数，首项系数（即最高次幂对应的系数）均为 $1$，并且上述欧几里得算法在计算它们的最大公因式时恰好执行 $n$ 步。此外，第一个多项式的次数必须大于第二个多项式的次数。算法的每一步指从数对 $(P(x), Q(x))$ 转换到 $(Q(x), P(x) \bmod Q(x))$。
你将获得一个整数 $n$（$1 \leq n \leq 150$）——你需要达到的算法步数。
请按以下格式输出两个多项式。
第一行输出一个整数 $m$（$0 \leq m \leq n$）——多项式的次数。
第二行输出 $m+1$ 个介于 $-1$ 和 $1$ 之间的整数——从常数项到首项的系数。
第一个多项式的次数必须大于第二个多项式的次数，且两个多项式的首项系数都必须为 $1$。欧几里得算法在使用这两个多项式时必须恰好执行 $n$ 步。
如果对于给定的 $n$ 无解，请输出 _-1_。
如果有多个解，输出任意一个即可。
在第二个例子中，你可以输出多项式 $x^2 - 1$ 和 $x$。其变换序列为
$$(x^2 - 1, x) \to (x, -1) \to (-1, 0)$$
共两步。
## Input
你将获得一个整数 $n$（$1 \leq n \leq 150$）——你需要达到的算法步数。
## Output
请按以下格式输出两个多项式。第一行输出一个整数 $m$（$0 \leq m \leq n$）——多项式的次数。第二行输出 $m+1$ 个介于 $-1$ 和 $1$ 之间的整数——从常数项到首项的系数。第一个多项式的次数必须大于第二个多项式的次数，且两个多项式的首项系数都必须为 $1$。欧几里得算法在使用这两个多项式时必须恰好执行 $n$ 步。如果对于给定的 $n$ 无解，请输出 _-1_。如果有多个解，输出任意一个即可。
[samples]
## Note
在第二个例子中，你可以输出多项式 $x^2 - 1$ 和 $x$。其变换序列为
$$(x^2 - 1, x) \to (x, -1) \to (-1, 0)$$
共两步。
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 1 \leq n \leq 150 $.
**Constraints**
Find two polynomials $ P(x), Q(x) \in \mathbb{Z}[x] $ such that:
1. $ \deg(P) > \deg(Q) $, and $ \deg(P), \deg(Q) \leq n $,
2. All coefficients of $ P(x) $ and $ Q(x) $ lie in $ \{-1, 0, 1\} $,
3. Leading coefficients of $ P(x) $ and $ Q(x) $ are $ 1 $,
4. The Euclidean algorithm for GCD applied to $ (P(x), Q(x)) $ performs exactly $ n $ steps, where each step is the transition $ (A(x), B(x)) \mapsto (B(x), A(x) \bmod B(x)) $,
5. $ Q(x) \not\equiv 0 $.
**Objective**
Output:
- First polynomial: degree $ m_1 $, coefficients $ [c_0, c_1, \dots, c_{m_1}] $ (constant to leading),
- Second polynomial: degree $ m_2 $, coefficients $ [d_0, d_1, \dots, d_{m_2}] $ (constant to leading),
such that the above constraints are satisfied.
If no such pair exists, output `-1`.
API Response (JSON)
{
"problem": {
"name": "D. GCD of Polynomials",
"description": {
"content": "Suppose you have two polynomials and . Then polynomial can be uniquely represented in the following way: This can be done using [long division](https://en.wikipedia.org/wiki/Polynomial_long_division)",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF902D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Suppose you have two polynomials and . Then polynomial can be uniquely represented in the following way:\n\nThis can be done using [long division](https://en.wikipedia.org/wiki/Polynomial_long_division)...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "假设你有两个多项式 $P(x)$ 和 $Q(x)$。那么多项式 $P(x)$ 可以唯一地表示为如下形式：\n\n$$\nP(x) = Q(x) \\cdot D(x) + R(x)\n$$\n\n这可以通过长除法完成。这里，$\\deg(P(x))$ 表示多项式 $P(x)$ 的次数。$R(x)$ 称为 $P(x)$ 除以 $Q(x)$ 的余数，也记作 $P(x) \\bmod Q(x)$。\n\n由于存在带余除法，我...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 150 $. \n\n**Constraints** \nFind two polynomials $ P(x), Q(x) \\in \\mathbb{Z}[x] $ such that: \n1. $ \\deg(P) > \\deg(Q) $, and $ \\deg(P), ...",
"is_translate": false,
"language": "Formal"
}
]
}