AC日记——「HNOI2017」礼物 LiBreOJ 2020

#2020. 「HNOI2017」礼物

思路：

　　A题进程；

　　一眼出式子->各种超时过不去->看题解明白还有fft这个东西->百度文库学习fft->学习dft->学习fft->死活写不出代码->比着大佬博客敲代码->ac->不容易啊。。

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 500005

#define INF 0x3f3f3f3f

const double pi=acos(-);

struct Complex

{

    double r,i;

    Complex(double r,double i=):r(r),i(i){}

    Complex(){}

};

Complex operator+(Complex a,Complex b)

{

    return Complex(a.r+b.r,a.i+b.i);

}

Complex operator-(Complex a,Complex b)

{

    return Complex(a.r-b.r,a.i-b.i);

}

Complex operator*(Complex a,Complex b)

{

    return Complex(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);

}

int n,m,data1[maxn],data2[maxn],rev[maxn],ans=INF;

Complex ai[maxn],bi[maxn],ai2[maxn],bi2[maxn];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'')Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void fft(Complex *res,int l,int p)

{

    for(int i=;i<l;i++) if(i<rev[i]) swap(res[i],res[rev[i]]);

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

    {

        Complex wd=Complex(cos(pi/i),sin(pi/i)*p);

        for(int v=;v<l;v+=(i<<))

        {

            Complex w=Complex(,);

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

            {

                Complex tmp=res[v+k],tmp_=w*res[v+k+i];

                res[v+k]=tmp+tmp_,res[v+k+i]=tmp-tmp_;

                w=w*wd;

            }

        }

    }

    if(p==-) for(int i=;i<l;i++) res[i].r/=l,res[i].i/=l;

}

int main()

{

    freopen("data.txt","r",stdin);

    in(n),in(m);

    int mxn,lg=,s=;

    for(mxn=;mxn<=n*;mxn*=,lg++);

    for(int i=;i<mxn;i++) rev[i]=(rev[i>>]>>)|((i&)<<(lg-));

    for(int i=;i<=n;i++) in(data1[i]),ai[i]=data1[i],ai2[n-i+]=data1[i];

    for(int i=;i<=n;i++) in(data2[i]),bi[n-i+]=data2[i],bi2[i]=data2[i],s+=data2[i];

    fft(bi,mxn,),fft(bi2,mxn,),fft(ai,mxn,),fft(ai2,mxn,);

    for(int i=;i<mxn;i++) ai[i]=ai[i]*bi[i],ai2[i]=ai2[i]*bi2[i];

    fft(ai,mxn,-),fft(ai2,mxn,-);

    for(int l=-m+;l<m;l++)

    {

        int w=;

        for(int i=;i<=n;i++) w+=(data1[i]+l)*(data1[i]+l)+data2[i]*data2[i];

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

        {

            int v=(int)(ai[i].r+0.1)+(int)(ai2[n-i+].r+0.1)+s*l;

            ans=min(ans,w-*v);

        }

    }

    printf("%d\n",ans);

    return ;

}