luoguP3723 HNOI2017 礼物
-
首先，两个手环增加非负整数亮度，等于其中一个增加一个整数亮度，可以为负。
-
令增加量为(x)，旋转以后的原数列为，那么在不考虑转圈圈的情况下，现在的费用就是：
[sum_{i=1}^nleft(a_i+x-b_i
ight)^2
]
- 即
[sum_{i=1}^na_i^2+sum_{i=1}^nb_i^2+nx^2+2xleft(sum_{i=1}^na_i-sum_{i=1}^nb_i
ight)-2sum_{i=1}^na_ib_i
]
- 前面两个是确定的，后面是(y=ax^2+bx+c)的形式，那么(x=frac{b}{-2a})。
- 所以只需要使得(sum a_i*b_i)最大即可。
- 直接做不好做，翻转(a)：
[sum_{i=1}^na_{n-i+1}b_i
]
- 这不是一个卷积吗~
- 把(b)倍长后，其中卷起来后的每一项都对应了一种反转方案，直接(fft)后取最小值。
- 然后把前面的不变项加上，就是答案了。
#include<bits/stdc++.h>
#define R register int
#define db double
#define il inline
#define ll long long
using namespace std;
const int N=1000000;
const db pi=acos(-1.0);
int n,m,x,nw,pik,a[N],b[N];ll ans;
il int gi(){
R x=0,k=1;char c=getchar();
while(c!='-'&&(c<'0'||c>'9'))c=getchar();
if(c=='-')k=-1,c=getchar();
while(c<='9'&&c>='0')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*k;
}
il int sqr(R x){return x*x;}
namespace FFT{
int m,lim=1,er,Mx=-2e9,rd[N];
struct G{
db x,y;
G (db xx=0,db yy=0){x=xx,y=yy;}
}x[N],y[N];
G operator + (G a,G b){return G(a.x+b.x,a.y+b.y);}
G operator - (G a,G b){return G(a.x-b.x,a.y-b.y);}
G operator * (G a,G b){return G(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void fft(G *A,R op){
for(R i=0;i<lim;++i)if(i<rd[i])swap(A[i],A[rd[i]]);
for(R mid=1;mid<lim;mid<<=1){
G Wn(cos(pi/mid),op*sin(pi/mid));
for(R len=mid<<1,j=0;j<lim;j+=len){
G W(1,0);
for(R k=0;k<mid;++k,W=W*Wn){
G x=A[j+k],y=W*A[j+k+mid];
A[j+k]=x+y,A[j+k+mid]=x-y;
}
}
}
}
ll sol(){
reverse(a+1,a+n+1),m=n+n;
for(R i=0;i<n;++i)x[i].x=a[i+1],y[i].x=b[i+1];
for(R i=n;i<n+n;++i)y[i]=y[i-n];
while(lim<=n+m)lim<<=1,er++;
for(R i=0;i<lim;++i)rd[i]=(rd[i>>1]>>1)|((i&1)<<(er-1));
fft(x,1),fft(y,1);
for(R i=0;i<lim;++i)x[i]=x[i]*y[i];
fft(x,-1);
for(R i=0;i<lim;++i)Mx=max(Mx,(int)(x[i].x/lim+0.5));
return Mx;
}
}
int main(){
n=gi(),m=gi();
for(R i=1;i<=n;++i)a[i]=gi(),ans+=sqr(a[i]),x-=a[i];
for(R i=1;i<=n;++i)b[i]=gi(),ans+=sqr(b[i]),x+=b[i];
nw=-x,x/=n,x--,pik=n*sqr(x)+2*x*nw;
x++,pik=min(pik,n*sqr(x)+2*x*nw);
x++,pik=min(pik,n*sqr(x)+2*x*nw);
ans+=pik-(FFT::sol()<<1),cout<<ans<<endl;
return 0;
}