首页 > 代码库 > [BZOJ 3527][Zjoi2014]力（FFT）

[BZOJ 3527][Zjoi2014]力（FFT）

2024-09-20 20:23:18   203人阅读

Description

给出n个数qi，给出Fj的定义如下：
技术分享
令Ei=Fi/qi，求Ei.

Solution

设fi=qi gi=1/i/i（这里如果写成i*i可能会爆int）

那前半部分就是∑fi*gj-i 发现是一个卷积的形式

后半部分把数组反一下同理

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#define MAXN 100005#define pi acos(-1)using namespace std;int n;struct cp{    double r,i;    cp(double r=0,double i=0):r(r),i(i){}    cp operator + (const cp& x)    {return cp(r+x.r,i+x.i);}    cp operator - (const cp& x)    {return cp(r-x.r,i-x.i);}    cp operator * (const cp& x)    {return cp(r*x.r-i*x.i,r*x.i+i*x.r);}}a[MAXN*4],b[MAXN*4],c[MAXN*4];void brc(cp* x,int l){    int k=l/2;    for(int i=1;i<l-1;i++)    {        if(i<k)swap(x[i],x[k]);        int j=l/2;        while(k>=j)        {            k-=j;            j>>=1;        }        if(k<j)k+=j;    }}void fft(cp* x,int l,int on){    brc(x,l);    for(int h=2;h<=l;h<<=1)    {        cp wn(cos(2*on*pi/h),sin(2*on*pi/h));        for(int i=0;i<l;i+=h)        {            cp w(1,0);            for(int j=i;j<i+h/2;j++)            {                cp u=x[j];                cp t=x[j+h/2]*w;                x[j]=u+t;                x[j+h/2]=u-t;                w=w*wn;            }        }    }    if(on==-1)for(int i=0;i<l;i++)x[i].r/=l;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        double t;        scanf("%lf",&t);        a[i]=cp(t,0);        b[n-i+1]=cp(t,0);        c[i]=cp(1.0/i/i,0);    }    int l=1;    while(l<n*2)l<<=1;    fft(a,l,1),fft(b,l,1),fft(c,l,1);    for(int i=0;i<l;i++)    a[i]=a[i]*c[i],b[i]=b[i]*c[i];    fft(a,l,-1),fft(b,l,-1);    for(int i=1;i<=n;i++)    {        double ans=a[i].r-b[n+1-i].r;        printf("%lf\n",ans);    }    return 0;}

 

[BZOJ 3527][Zjoi2014]力（FFT）


联系
我们