Description
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 $n$ 个装饰物，并且每个装饰物都有一定的亮度。
但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的非负整数 $c$。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。
在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1 sim n$，其中 $n$ 为每个手环的装饰物个数， 第 $1$ 个手环的 $i$ 号位置装饰物亮度为 $x_i$，第 $2$ 个手环的 $i$ 号位置装饰物亮度为 $y_i$，两个手环之间的差异值为（参见输入输出样例和样例解释）：
$$sum_{i=1}^{n} (x_i-y_i)^2$$
麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？
Solution
假设此时已经进行完旋转操作，对某一多项式每一项加$c$
$$sum _{i=0}^{n-1} (x_i-y_i+c)^2 = nc^2+2csum _{i=0}^{n-1} (x_i-y_i)+sum _{i=0}^{n-1}x_i+sum _{i=0}^{n-1} y_i-2sum _{i=0}^{n-1}x_iy_i$$
观察到前两项为二次函数，取极值即可，第三第四项很好算，现在只需解决旋转的问题
如果将$a$逆序，转化为多项式相乘的问题
FFT求解
#include<algorithm> #include<iostream> #include<complex> #include<cstdio> #include<cmath> using namespace std; int n,m,rev[400005]; long long ans,temp,tot=1,s=2; const double pie=acos(-1); complex<double>a[400005],b[400005]; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } void fft(complex<double>*a,int N,int inv) { for(int i=0;i<N;i++) if(i<rev[i]) swap(a[i],a[rev[i]]); for(int i=1;i<N;i*=2) { complex<double>wn=exp(complex<double>(0,inv*pie/i)); for(int j=0;j<N;j+=i*2) { complex<double>w(1,0); for(int k=j;k<j+i;k++) { complex<double>x=a[k],y=w*a[k+i]; a[k]=x+y,a[k+i]=x-y,w*=wn; } } } if(inv==-1) for(int i=0;i<N;i++) a[i]/=N; } int main() { n=read(),m=read(); for(int i=0;i<n;i++) a[i]=read(); for(int i=0;i<n;i++) b[i]=read(); for(int i=0;i<n;i++) ans+=a[i].real()*a[i].real()+b[i].real()*b[i].real(),temp+=b[i].real()-a[i].real(); int p1=floor((double)temp/(double)n),p2=ceil((double)temp/(double)n); ans+=min(n*p1*p1-2*p1*temp,n*p2*p2-2*p2*temp); for(int i=0;i<n;i++) b[i+n]=b[i]; reverse(a,a+n); while((1<<tot)<(3*n)) s<<=1,tot++; for(int i=0;i<s;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(tot-1)); fft(a,s,1),fft(b,s,1); for(int i=0;i<s;i++) a[i]*=b[i]; fft(a,s,-1),temp=0; for(int i=n-1;i<2*n-1;i++) temp=max(temp,(long long)(a[i].real()+0.5)); printf("%lld ",ans-(temp<<1)); return 0; }