Discrete Fourier Transform#5901
In this problem, your task is to compute the discrete Fourier transform (DFT) of a polynomial. The DFT is represented as a vector y = (y_0, y_1, \ldots, y_{n-1}), where each coefficient is determined by the formula:
The input begins with a single integer (1 \leq n \leq 1000). The following line contains exactly integers, which are the coefficients a_k (-1000 \leq a_k \leq 1000), listed in order from a_0 to a_{n-1}.
The output should consist of exactly lines. Each line should display two numbers: \mathrm{real}(y_k) and \mathrm{imag}(y_k), separated by a space. These values must be presented with an absolute or relative error not exceeding 10^{-6}. Here, refers to the real part, and refers to the imaginary part of the complex number.
Example 1
Example 2