BZOJ-3527: [Zjoi2014]力

Description

给出n个数qi，给出Fj的定义如下令Ei=Fi/qi，求Ei

等价于区间卷上序列
将序列从0前后分开，FFT求两段卷积即可。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
const double pi=acos(-1.0);
struct cp
{
    double x,i;
    cp(double _x=0,double _i=0):x(_x),i(_i){}
    cp operator +(const cp z)const {return cp(x+z.x,i+z.i);}
    cp operator -(const cp z)const {return cp(x-z.x,i-z.i);}
    cp operator *(const cp z)const {return cp(x*z.x-i*z.i,x*z.i+i*z.x);}
};
void FFT(cp a[],int len,int fl)
{
    int i,j,k; cp t;
    for(i=k=0;i<len;++i)
    {
        if(i>k) swap(a[i],a[k]);
        for(j=(len>>1);(k^=j)<j;j>>=1);
    }
    for(i=2;i<=len;i<<=1)
    {
        cp wn(cos(2*pi*fl/i),sin(2*pi*fl/i));
        for(j=0;j<len;j+=i)
        {
            cp w(1,0);
            for(k=j;k<j+(i>>1);++k,w=w*wn)
                t=w*a[k+(i>>1)],a[k+(i>>1)]=a[k]-t,a[k]=a[k]+t;
        }
    }
    if(fl==-1) for(i=0;i<len;++i) a[i].x/=len;
}

int n;
double q[N];
cp f[N<<2],g1[N<<2],g2[N<<2];
int main()
{
    scanf("%d",&n);
    int i,len;
    for(len=1;len<(n*2);len<<=1);
    for(i=0;i<n;++i) scanf("%lf",&f[i].x);
    for(i=0;i<n;++i) g1[i].x=1.0/(1.0+i)/(1.0+i),g2[i].x=1.0/(n-i)/(n-i);
    FFT(f,len,1); FFT(g1,len,1); FFT(g2,len,1);
    for(i=0;i<len;++i) g1[i]=g1[i]*f[i],g2[i]=g2[i]*f[i];
    FFT(g1,len,-1); FFT(g2,len,-1);
    for(i=1;i<=n;++i)
        printf("%.3lf\n",i>=2 ? g1[i-2].x-g2[n+i-1].x : -g2[n+i-1].x);
    return 0;
}