[bzoj3527][Zjoi2014]力

来自FallDream的博客，未经允许，请勿转载，谢谢。

---

给定n(n<=100000)个数qi

求Ei=Fi/qi

题解：首先约去所有的qi，然后就是一个卷积了，Ai=qi,Bi=1/i^2搞一次，然后把A倒过来搞一次，套上FFT就行了。

#include<iostream>
#include<cstdio>
#include<cmath>
#define pi acos(-1)
#define MN 262150
using namespace std;
inline int read()
{
    int x = 0 , f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

struct cp{
    double r,u;
    cp(double x=0,double y=0):r(x),u(y){}
    cp operator+(const cp&y)const{return cp(r+y.r,u+y.u);}
    cp operator-(const cp&y)const{return cp(r-y.r,u-y.u);}
    cp operator/(double y){return cp(r/y,u/y);}
    cp operator*(const cp&y)const{return cp(r*y.r-u*y.u,r*y.u+u*y.r);}
}a[MN+5],b[MN+5],c[MN+5],w[2][MN+5];

int n,N;
double ans[MN+5];

void fft(cp*x,int b)
{
    for(int i=0,j=0;i<n;i++)
    {
        if(i>j)swap(x[i],x[j]);
        for(int k=n>>1;(j^=k)<k;k>>=1);
    }
    for(int i=2;i<=n;i<<=1)for(int j=0;j<n;j+=i)for(int k=0;k<i>>1;k++)
    {
        cp t=x[j+k+(i>>1)]*w[b][n/i*k];
        x[j+k+(i>>1)]=x[j+k]-t;
        x[j+k]=x[j+k]+t; 
    }
    if(b) for(int i=0;i<n;i++) x[i]=x[i]/(double)n;
}

int main()
{
    N=read();for(n=1;n<N;n<<=1);n<<=1;
    for(int i=1;i<=N;i++)scanf("%lf",&a[i].r);
    w[0][0]=w[1][n]=cp(1,0);w[0][1]=w[1][n-1]=cp(cos(2*pi/n),sin(2*pi/n));
    for(int i=2;i<=n;i++) w[0][i]=w[1][n-i]=w[0][i-1]*w[0][1];
    for(int i=1;i<=N;i++)c[i]=a[N+1-i];
    for(int i=1;i<=N;i++)b[i].r=(double)1/(1LL*i*i);
    fft(a,0);fft(b,0);fft(c,0);
    for(int i=0;i<n;i++) c[i]=b[i]*c[i],a[i]=a[i]*b[i];
    fft(c,1);fft(a,1);
    for(int i=1;i<=N;i++) printf("%.6lf
",a[i].r-c[N-i+1].r); 
    return 0;
}