Eva

Time Limit: 30 Sec  Memory Limit: 256 MBSec  Special Judge
Description

给出n个数qi，给出Fj的定义如下：

令Ei=Fi/qi，求Ei.

Input

第一行一个整数n。

接下来n行每行输入一个数，第i行表示qi。

n≤100000，0<qi<1000000000

Output 

n行，第i行输出Ei。与标准答案误差不超过1e-2即可。

Sample Input

5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880

Sample Output

-16838672.693
3439.793
7509018.566
4595686.886
10903040.872

/**************************************************************

    Problem: 3527

    User: mywaythere

    Language: C++

    Result: Accepted

    Time:4876 ms

    Memory:17192 kb

****************************************************************/

 

#include <cstdio>

#include <algorithm>

#include <complex>

 

using namespace std;

 

typedef complex<double> Complex;

#define LL long long

const int maxn = 1 << 18;

 

const double PI = acos(-1.0);

void FFT(Complex P[], int n, int oper)

{

    for (int i = 1, j = 0; i < n - 1; i++) {

        for (int s = n; j ^= s >>= 1, ~j & s;);

        if (i < j) swap(P[i], P[j]);

    }

    Complex unit_p0;

    for (int d = 0; (1 << d) < n; d++) {

        int m = 1 << d, m2 = m * 2;

        double p0 = PI / m * oper;

        unit_p0 = Complex(cos(p0), sin(p0));

        for (int i = 0; i < n; i += m2) {

            Complex unit = 1;

            for (int j = 0; j < m; j++) {

                Complex &P1 = P[i + j + m], &P2 = P[i + j];

                Complex t = unit * P1;

                P1 = P2 - t;

                P2 = P2 + t;

                unit = unit * unit_p0;              

            }

        }

    }

}

 

int n;

Complex x[maxn], y[maxn], z[maxn], c[maxn];

 

inline double squ(double k)

{

    return k * k;

}

 

int main()

{

    scanf("%d", &n);

    for (int i = 0; i < n; i++)

        scanf("%lf", &x[i]);

    for (int i = 0; i < n; i++)

        y[i] = -1.0 / squ(n - i);

    y[n] = 0;

    for (int i = n + 1; i <= 2 * n; i++)

        y[i] = 1.0 / squ(i - n);

         

    int MXN = 1;

    while (MXN < n * 2 + 1)

        MXN *= 2;

    //printf("%d\n", MXN);

    for (int i = n; i < MXN; i++)

        x[i] = 0;

    for (int i = 2 * n + 1; i < MXN; i++)

        y[i] = 0;

         

    FFT(x, MXN, 1);

    FFT(y, MXN, 1);

    for (int i = 0; i < MXN; ++i)

        z[i] = x[i] * y[i];

    FFT(z, MXN, -1);

    for (int i = 0; i < MXN; ++i)

        c[i] = z[i].real() / MXN;

    for (int i = 0; i < n; i++)

        printf("%.3f\n", c[n + i].real());

     

    return 0;

}