bzoj 4827 礼物(fft)

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

分析：

初看题目毫无思路     写了写式子后发现是fft     推导过程如下(敲出来太麻烦直接手写了)

观察最后的式子发现这是一个关于c的一元二次方程     可知最小值在对称轴处取得     所以便可得知c的大小

然后发现最后一项若将y数组逆置便是卷积形式   用fft求出即可    由题意可知应为循环卷积      将x数组倍增   求出循环卷积    然后枚举出每个方程的最小值     取得最小便是答案

AC代码：

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include<list>
#include <bitset>
#include <climits>
#include <algorithm>
#define gcd(a,b) __gcd(a,b)
#define FIN	freopen("input.txt","r",stdin)
#define FOUT 	freopen("output.txt","w",stdout)
typedef long long LL;
const LL mod=1e9+7;
const int INF=0x3f3f3f3f;
const double pi=acos(-1.0);
using namespace std;
struct complex{//            运算符重载
    double a,b;
    complex(double a=0,double b=0){this->a=a;this->b=b;}
    complex operator + (complex &p){return complex(a+p.a,b+p.b);}
    complex operator - (complex &p){return complex(a-p.a,b-p.b);}
    complex operator * (complex &p){return complex(a*p.a-b*p.b,a*p.b+b*p.a);}
}x[200005],y[200005];
void Rader(complex a[],int len){//       倒位序
    int k;
    for (int i=1,j=len/2;i<len-1;i++){
        if(i<j) swap(a[i],a[j]);
        k=len/2;
        while (j>=k){
            j-=k;
            k/=2;
        }
        if(j<k) j+=k;
    }
}
void fft(complex a[],int len,int oper){//                     快速傅里叶变换
    Rader(a,len);//     对a进行倒位序
    for (int h=2;h<=len;h<<=1){
        complex wn(cos(-oper*2*pi/h),sin(-oper*2*pi/h));
        for (int j=0;j<len;j+=h){
            complex w(1,0);
            for (int k=j;k<j+h/2;k++){
                complex u=a[k];
                complex t=w*a[k+h/2];
                a[k]=u+t;
                a[k+h/2]=u-t;
                w=w*wn;
            }
        }
    }
    if(oper==-1)
    for (int i=0;i<len;i++)
        a[i].a/=len;
}
int main (){
        int n,m;
       // FIN;
        scanf ("%d%d",&n,&m);
        int len=1;
        double sumx=0,sumy=0;
        double c=0;
        double tt=0;
        double ans=INF;
        while (len<2*n)   len<<=1;
        int temp;
        for (int i=0;i<n;i++){
            scanf ("%d",&temp);
            x[i]=x[i+n]=complex(temp,0);
            sumx+=temp*temp;
            tt-=temp;
        }
        for (int i=0;i<n;i++){
            scanf ("%d",&temp);
            y[n-1-i]=complex(temp,0);
            sumy+=temp*temp;
            tt+=temp;
        }
        c=round(tt/n);//                    求 C
        fft(x,len,1);
        fft(y,len,1);
        for (int i=0;i<len;i++)
            x[i]=x[i]*y[i];
        fft(x,len,-1);
        for (int i=0;i<len;i++){
            ans=min(ans,n*c*c-2*c*tt+sumx+sumy-2*(x[i].a+0.1));
        }
        printf ("%.0lf\n",ans);
    return 0;
}