Codeforces Round 453 (Div. 1) |
---|
Закончено |
Допустим, у вас есть два многочлена и
. Тогда многочлен
можно единственным образом представить в виде
Это может быть сделано делением в столбик. В этой записи обозначает степень многочлена P(x).
при этом будем называть остатком от деления многочлена
на многочлен
и обозначать
.
Раз есть способ разделить один многочлен на другой с остатком, то можно определить и алгоритм Евклида для нахождения наибольшего общего делителя двух многочленов. Алгоритм определён таким образом, что он принимает пару многочленов , а затем если многочлен
нулевой, то алгоритм возвращает многочлен
, а иначе возвращает результат выполнения алгоритма для пары
. На каждом шаге степень второго аргумента уменьшается, поэтому алгоритм отработает за конечное число шагов. Но насколько большим оно может быть? Это вам и предстоит выяснить.
Вам дано число n. Вам нужно вывести два многочлена степени не выше n таких, что их коэффициенты — целые числа, не превышающие 1 по абсолютной величине, при этом старший коэффициент (при максимальной степени x) должен быть равен единице, и вычисление их наибольшего общего делителя потребует ровно n шагов алгоритма Евклида. Кроме того, степень первого многочлена должна быть больше степени второго. Шагом алгоритма Евклида мы называем переход от к
.
На вход дано единственное целое число n (1 ≤ n ≤ 150) — число шагов алгоритма Евклида, которого требуется достичь.
Выведите два многочлена в следующем формате.
В первой строке выведите число m (0 ≤ m ≤ n) — степень многочлена.
Во второй строке выведите m + 1 целых чисел от - 1 до 1 — коэффициенты многочлена, от младшего к старшему.
Степень первого многочлена должна быть больше степени второго, а старшие коэффициенты обоих многочленов должны быть равны 1. Алгоритм Евклида, вызванный от этих многочленов должен занимать ровно n шагов.
Если для данного числа n ответа не существует, выведите -1.
Если есть несколько возможных вариантов ответа, выведите любой из них.
1
1
0 1
0
1
2
2
-1 0 1
1
0 1
Во втором тестовом примере можно вывести многочлены x2 - 1 и x. Тогда цепочка вызовов будет
Она состоит из ровно двух шагов.
Название |
---|