[文章目录]
Description
每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。他使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面 装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。两个手环之间的差异值为：麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小， 这个最小值是多少呢？
等价于
分开计算，为常数，倍增一个之后FFT求卷积，找最大值，一元二次函数求最小值，c等于，取最相近的两个整数点计算最小值。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 51000
typedef long long ll;
ll ans;
int n,x[N],y[N];
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);}
}f1[N<<2],f2[N<<2];
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 main()
{
scanf("%d%*d",&n);
int i,sx=0,sy=0;
for(i=1;i<=n;++i) scanf("%d",x+i),sx+=x[i],ans+=x[i]*x[i];
for(i=1;i<=n;++i) scanf("%d",y+i),sy+=y[i],ans+=y[i]*y[i];
int c=(sy-sx)/n;
ans+=min(2ll*c*(sx-sy)+(ll)n*c*c,2ll*(c+1)*(sx-sy)+(ll)n*(c+1)*(c+1));
int len;
for(len=1;len<(2*n);len<<=1);
for(i=0;i<n;++i) f1[i].x=f1[i+n].x=x[i+1];
for(i=0;i<n;++i) f2[i].x=y[n-i];
FFT(f1,len,1); FFT(f2,len,1);
for(i=0;i<len;++i) f1[i]=f1[i]*f2[i];
FFT(f1,len,-1);
int tmp=-1<<30;
for(i=n-1;i<=(n<<1)-2;++i)
tmp=max(tmp,int(f1[i].x+0.1));
ans=ans-2ll*tmp;
printf("%lld",ans);
return 0;
}