解题思路

　　首先我们设变化量为\(r\)，那么最终的答案就可以写成 ：

\[ ans=min(\sum\limits_{i=1}^n(a_i-b_i+r)^2) \]

\[ ans=min(\sum\limits_{i=1}^n(a_i-b_i)^2-2*r*\sum\limits_{i=1}^{n}(a_i-b_i)+n*r^2) \]

继续化简：

\[ ans=min(\sum\limits_{i=1}^n a_i^2+\sum\limits_{i=1}^n b_i^2-2*\sum\limits_{i=1}^na_i*b_i-2*r*\sum\limits_{i=1}^{n}(a_i-b_i)+n*r^2) \]

\[ ans=min((\sum\limits_{i=1}^n a_i^2+\sum\limits_{i=1}^n b_i^2)-(2*r*\sum\limits_{i=1}^{n}(a_i-b_i)+n*r^2)-(2*\sum\limits_{i=1}^na_i*b_i)) \]

这样我们就可以发现，第一部分是一个定值，第二部分只需要从\(-m\)到\(m\)枚举一下\(r\)就能算出，现在问题就是算第三部分。发现第三部分形式特别像卷积，就直接将\(a\)数组翻一下倍，表示旋转，\(b\)数字翻转一下。然后\(fft\)后算一个最大值即可。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN = 50005<<3;const double Pi=acos(-1);typedef long long LL;inline int rd(){  int x=0,f=1;char ch=getchar();  while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}  while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}  return f?x:-x;}int n,m,limit=1,rev[MAXN];LL ans,sqA,sqB,A,B,Sum=1e18;struct Complex{  double x,y;  Complex(double xx=0,double yy=0) {x=xx;y=yy;}}a[MAXN],b[MAXN];Complex operator +(const Complex A,const Complex B) {return Complex(A.x+B.x,A.y+B.y);}Complex operator -(const Complex A,const Complex B) {return Complex(A.x-B.x,A.y-B.y);}Complex operator *(const Complex A,const Complex B) {return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);}inline void fft(Complex *f,int type){  for(int i=0;i
         
          >1;Wn=Complex(cos(Pi/len),type*sin(Pi/len)); for(int k=0;k
          
           >1]>>1)|((i&1)?limit>>1:0); fft(a,1);fft(b,1);for(int i=0;i