bzoj 4827 [Hnoi2017]礼物——FFT

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4827

式子就是 \sum_{i=0}^{n-1}(a[ i ] - b[ i+k ] + c)^2 。把 b 翻成两倍后卷积即可。关于 c 的部分是一个二次函数，注意 c 只能是整数！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define db double

using namespace std;

const int N=5e4+,M=N*;

const db pi=acos(-);

int n,m,sm,len,ca,cb,r[M];

struct cpl{db x,y;}a[M],b[M],I;

cpl operator+ (cpl a,cpl b){return (cpl){a.x+b.x,a.y+b.y};}

cpl operator- (cpl a,cpl b){return (cpl){a.x-b.x,a.y-b.y};}

cpl operator* (cpl a,cpl b){return (cpl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void fft(cpl *a,bool fx)

{

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

    if(i<r[i])swap(a[i],a[r[i]]);

  for(int R=;R<=len;R<<=)

    {

      int m=R>>;

      cpl Wn=(cpl){ cos(pi/m),fx?-sin(pi/m):sin(pi/m) };

      for(int i=;i<len;i+=R)

    {

      cpl w=I;

      for(int j=;j<m;j++,w=w*Wn)

        {

          cpl tmp=w*a[i+m+j];

          a[i+m+j]=a[i+j]-tmp;

          a[i+j]=a[i+j]+tmp;

        }

    }

    }

}

int main()

{

  n=rdn();m=rdn(); I.x=;

  for(int i=n-;i>=;i--)

    {

      a[i].x=rdn();sm+=a[i].x*a[i].x;ca+=a[i].x;

    }

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

    {

      b[i].x=b[i+n].x=rdn();sm+=b[i].x*b[i].x;cb+=b[i].x;

    }

  int c=floor((db)(cb-ca)/n),tmp=n*c*c+*(ca-cb)*c;

  c++; tmp=min(tmp,n*c*c+*(ca-cb)*c);

  sm+=tmp;

  len=;

  for(;len<=n*;len<<=);

  for(int i=;i<len;i++)r[i]=(r[i>>]>>)+((i&)?len>>:);

  fft(a,); fft(b,);

  for(int i=;i<len;i++)a[i]=a[i]*b[i];

  fft(a,); tmp=;

  for(int i=(n<<)-;i>=n-;i--)

    tmp=max(tmp,int(a[i].x/len+0.5));

  sm-=tmp<<;

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

  return ;

}