← 返回题目列表

Codeforces · 901/B

B. 多项式的 GCD

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

假设您有两个多项式 $$A(x) = \sum_{k=0}^{n} a_k x^k$$ 和 $$B(x) = \sum_{k=0}^{m} b_k x^k$$。那么多项式$$A(x)$$可以通过以下方式唯一表示:

$$A(x) = B(x) \cdot D(x) + R(x), \deg R(x) < \deg B(x).$$

这可以使用长除法来完成。这里,$$\deg P(x)$$表示多项式P(x)的次数。 $$R(x)$$称为多项式$$A(x)$$除以多项式$$B(x)$$的余数,也记为$$A \bmod B$$。

由于有一种方法可以将多项式除以余数,因此我们可以定义欧几里得算法来查找两个多项式的最大公约数。该算法采用两个多项式$$(A,B)$$。如果多项式 $$B(x)$$ 为零,则结果为 $$A(x)$$,否则结果为算法为 $$( B, A \bmod B )$$ 对返回的值。在每一步中,第二个参数的次数都会减少,因此该算法以有限数量的步骤运行。但这个数字有多大呢?你要回答这个问题。

给定一个整数 n。您必须建立两个次数不大于 n 的多项式,使得它们的系数是绝对值不超过 1 的整数,前导系数(具有最大 x 次方的系数)等于 1,并且所描述的欧几里得算法恰好执行 n 个步骤来查找其最大公约数。此外,第一个多项式的次数应大于第二个多项式的次数。算法的一步是指从 $$(A,B)$$ 到 $$( B, A \bmod B )$$ 的转换。

输入

给您一个整数 n (1 ≤ n ≤ 150) — 您需要达到的算法步骤数。

输出

按以下格式打印两个多项式。

在第一行中打印一个整数 m (0 ≤ m ≤ n) — 多项式的次数。

在第二行中打印 m + 1 个介于 - 1 和 1 之间的整数 — 多项式的系数,从常数到前导。

第一个多项式的次数应大于第二个多项式的次数,前导系数应等于 1。当使用这些多项式调用时,欧几里得算法应恰好执行 n 个步骤。

如果给定的 n 没有答案,则打印 -1。

如果有多个答案,则打印其中任何一个。

示例

输入 #1

1

输出 #1

1
0 1
0
1

输入 #2

2

输出 #2

2
-1 0 1
1
0 1

注意

在第二个示例中,您可以打印多项式 x2 - 1 和 x。转换的顺序是

(x2 - 1, x) → (x, - 1) → ( - 1, 0)。

其中有两个步骤。