Побудова Поліномів#6204

Побудова Поліномів

1 секунда

64 мегабайти

Середня

Графічні калькулятори стали популярними серед учнів старших класів, оскільки дозволяють легко відображати функції на екрані. Однак, ці калькулятори зазвичай не мають дуже швидких процесорів. У цій задачі вам потрібно реалізувати метод для прискорення відображення полінома.

Дано поліном $p (x) = a_{n} x^{n} + ... + a_{1} x + a_{0}$ p(x) = a_nx^n + ... + a_1x + a_0 степеня $n$ . Ми хочемо обчислити значення цього полінома в $m$ цілих точках $x = 0, 1, ..., m - 1$ x = 0, 1, ..., m-1. Пряме обчислення в цих точках вимагає $mn$ множень і $mn$ додавань.

Один із способів прискорити обчислення — це використати раніше обчислені результати. Наприклад, якщо $p (x) = a_{1} x + a_{0}$ p(x) = a_1x + a_0 і $p (i)$ вже обчислено, тоді $p (i + 1) = p (i) + a_{1}$ p(i + 1) = p(i) + a_1. Таким чином, кожне наступне значення $p (x)$ можна обчислити за допомогою одного додавання.

Загалом, ми можемо обчислити $p (i + 1)$ p(i + 1) з $p (i)$ за допомогою $n$ додавань, після відповідної ініціалізації. Якщо ми ініціалізуємо константи $C_{0}$ C_0, $C_{1}$ C_1, ..., $C_{n}$ C_n відповідним чином, можна обчислити $p (i)$ за допомогою наступного псевдокоду:

$p (0) = C_{0}; t_{1} = C_{1}; ... t_{n} = C_{n};$ p(0) = C_0; t_1 = C_1; ... t_n = C_n;

$for i from 1 to m - 1 do$ \text{for } i \text{ from } 1 \text{ to } m-1 \text{ do}

$p (i) = p (i - 1) + t_{1};$ p(i) = p(i-1) + t_1;

$t_{1} = t_{1} + t_{2};$ t_1 = t_1 + t_2;

$t_{2} = t_{2} + t_{3};$ t_2 = t_2 + t_3;

$...$

$t_{n - 1} = t_{n - 1} + t_{n};$ t_{n-1} = t_{n-1} + t_n;

$end$

Наприклад, якщо $p (x) = a_{1} x + a_{0}$ p(x) = a_1x + a_0, ми можемо ініціалізувати $C_{0} = a_{0}$ C_0 = a_0 і $C_{1} = a_{1}$ C_1 = a_1.

Ваше завдання — обчислити константи $C_{0}$ C_0, $C_{1}$ C_1, ..., $C_{n}$ C_n для наведеного вище псевдокоду, щоб отримати правильні значення для $p (i)$ при $i = 0, ..., m - 1$ i = 0, ..., m - 1.

Вхідні дані

Вхід складається з одного випадку, заданого на одному рядку. Першим цілим числом є $n$ , де $1 \leq n \leq 6$ 1 \le n \le 6. За ним слідують $n + 1$ n+1 цілих коефіцієнтів $a_{n}$ a_n, ..., $a_{1}$ a_1, $a_{0}$ a_0. Ви можете припустити, що $∣ a_{i} ∣ \leq 50$ |a_i| \le 50 для всіх $i$ , і $a_{n} \neq = 0$ a_n \neq 0.

Вихідні дані

Виведіть цілі числа $C_{0}$ C_0, $C_{1}$ C_1, ..., $C_{n}$ C_n, розділені пробілами.

Приклади

Приклад 1