bzoj千题计划167：bzoj3527: [Zjoi2014]力

http://www.lydsy.com/JudgeOnline/problem.php?id=3527

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

令Ei=Fi/qi，求Ei.

 

 

 以n=4为例：

设数组a[],b[]

令c[]=a[]反转

y[]=c[]*b[]

那么E[i]=x[i]-y[n-i-1]

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 100001

const int M=<<;

const double pi=acos(-);

struct Complex

{

    double x,y;

    Complex() { }

    Complex(double _x,double _y) : x(_x),y(_y) { }

    Complex operator + (Complex  & P)

    {

        Complex C;

        C.x=x+P.x;

        C.y=y+P.y;

        return C;

    }

    Complex operator - (Complex & P)

    {

        Complex C;

        C.x=x-P.x;

        C.y=y-P.y;

        return C;

    }

    Complex operator * (Complex & P)

    {

        Complex C;

        C.x=x*P.x-y*P.y;

        C.y=x*P.y+y*P.x;

        return C;

    }

};

typedef Complex E;

int n;

int r[M];

E b[M];

E x[M],y[M];

void fft(E *a,int f)

{

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

        if(i<r[i]) swap(a[i],a[r[i]]);

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

    {

        E wn(cos(pi/i),f*sin(pi/i));

        for(int p=i<<,j=;j<n;j+=p)

        {

            E w(,);

            for(int k=;k<i;++k,w=w*wn)

            {

                E x=a[j+k],y=w*a[j+k+i];

                a[j+k]=x+y; a[j+k+i]=x-y;

            }

        }

    }

}

int main()

{

    int m,t;

    scanf("%d",&n);

    n--; m=t=n;

    double p;

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

    {

        scanf("%lf",&p);

        x[i].x=p;

        y[n-i].x=p;

    }

    for(int i=;i<=t;++i) b[i].x=1.0/i/i;

    m+=n;

    int bit=;

    for(n=;n<=m;n<<=) bit++;

    for(int i=;i<n;++i) r[i]=(r[i>>]>>)|((i&)<<bit-);

    fft(b,);

    fft(x,);

    for(int i=;i<n;++i) x[i]=x[i]*b[i];

    fft(x,-);

    fft(y,);

    for(int i=;i<n;++i) y[i]=y[i]*b[i];

    fft(y,-);

    for(int i=;i<=t;++i) printf("%.3lf\n",(x[i].x-y[t-i].x)/n);

}