CF901B GCD of Polynomials

设有两个多项式 $P(x)$ 和 $Q(x)$。则多项式 $P(x)$ 可以唯一表示为如下形式： $$ P(x) = Q(x) \cdot S(x) + R(x), $$ 其中 $R(x)$ 为 $P(x)$ 除以 $Q(x)$ 的余式，并满足 $\deg R(x) < \deg Q(x)$。这可以通过多项式的长除法实现。这里，$\deg P(x)$ 表示多项式 $P(x)$ 的次数。$R(x)$ 称为多项式 $P(x)$ 被多项式 $Q(x)$ 除的余式，也可记作 $P(x)\bmod Q(x)$。 由于多项式可以带余数相除，因此我们可以定义求解两个多项式最大公因式的欧几里得算法。该算法对给定两个多项式 $P(x)$ 和 $Q(x)$（其中 $\deg P(x) > \deg 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$。输入的 $n$，欧几里得算法对于这两个多项式要求恰好执行 $n$ 步。 若不存在解，输出 -1。 若存在多组解，输出任意一组均可。

在第二个样例中，可以输出多项式 $x^{2}-1$ 和 $x$。算法的转移序列如下所示： $$(x^{2}-1, x) \rightarrow (x, -1) \rightarrow (-1, 0).$$ 这样共执行了两步。 由 ChatGPT 5 翻译