Задачи
Дискретное преобразование Фурье
Дискретное преобразование Фурье
В этой задаче вам требуется провести дискретное преобразование Фурье для многочлена . Напомним, дискретное преобразование Фурье - это вектор y = (y_0, y_1, ..., y_{n-1}), коэффициенты которого вычисляются по формуле:
.
Входные данные
В первой строке записано единственное целое число n (1 ≤ n ≤ 1000). Во второй строке записано ровно n целых чисел - коэффициенты a_k (-1000 ≤ a_k ≤ 1000) в порядке от a_0 до a_{n-1}.
Выходные данные
Ввести ровно n строк. k-ая строка должна содержать ровно два числа real(y_k) и imag(y_k), разделенные пробелом и выведенные с абсолютной или относительной погрешностью, не превышающей 10^{-6}, где real() обозначает действительную часть, а imag() - мнимую.
Пример
Входные данные #1
2 1 2
Выходные данные #1
3.0000000000 0.0000000000 -1.0000000000 0.0000000000
Входные данные #2
4 1 2 3 4
Выходные данные #2
10.0000000000 0.0000000000 -2.0000000000 -2.0000000000 -2.0000000000 0.0000000000 -2.0000000000 2.0000000000