题解 P3723 【[AH2017/HNOI2017]礼物】
Orion545
2018-04-14 11:29:53
# 广告
### [蒟蒻のblog](http://www.cnblogs.com/dedicatus545/p/8831000.html)
# 正文
首先，有一个结论：两个手环增加非负整数亮度，等于其中一个增加一个整数亮度（可以为负）
我们令增加量为$x$，旋转以后的原数列为$\{a\}\{b\}$那么现在的费用就是：
### $\sum_{i=1}^n\left(a_i+x-b_i\right)^2$
我们把第i项拿出来拆开，得到：
### $\left(a_i+x-b_i\right)^2=a_i^2+b_i^2+x^2+2a_ix-2a_ib_i-2b_ix$
那么原式变成了
### $\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2+nx^2+2x\left(\sum_{i=1}^na_i-\sum_{i=1}^nb_i\right)-2\sum_{i=1}^na_ib_i$
我们发现，这个式子除了最后一项之外都是确定的QwQ
那么我们只要令最后一项最大，那么就可以得到最小的费用值了
### 现在问题转化为求$\sum_{i=1}^na_ib_i$的最大值
等等，这个形式......
我们把数列$\{a\}$反过来，变成
### $\sum_{i=1}^na_{n-i+1}b_i$
这不是一个卷积吗~
所以把反过来的数列$\{a\}$倍长，和数列$\{b\}$卷积，得到的项里面的第n+1到n\*2项的最大值，就是$\sum_{i=1}^na_ib_i$的最大值
然后把前面的不变项加上，就是答案了
Code：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define inf 1e15
using namespace std;
inline int read(){
int re=0,flag=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
struct complex{
double x,y;
complex(double xx=0,double yy=0){x=xx;y=yy;}
complex operator +(const complex &b){return complex(x+b.x,y+b.y);}
complex operator -(const complex &b){return complex(x-b.x,y-b.y);}
complex operator *(const complex &b){return complex(x*b.x-y*b.y,x*b.y+y*b.x);}
}A[400010],B[400010];
const double pi=acos(-1.0);
int n,m,limit=1,cnt=0,r[400010];
void fft(complex *a,double type){
int i,j,mid,k;complex x,y,w,wn;
for(i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);
for(mid=1;mid<limit;mid<<=1){
wn=complex(cos(pi/mid),type*sin(pi/mid));
for(j=0;j<limit;j+=(mid<<1)){
w=complex(1,0);
for(k=0;k<mid;k++,w=w*wn){
x=a[j+k];y=w*a[j+k+mid];
a[j+k]=x+y;a[j+k+mid]=x-y;
}
}
}
}
ll a1=0,a2=0,b1=0,b2=0,ans=inf;
int a[100010],b[100010];
int main(){
ll i,j;
n=read();m=read();
for(i=1;i<=n;i++){
a[i]=read();
a1+=a[i]*a[i];a2+=a[i];
}
for(i=1;i<=n;i++){
b[i]=read();
b1+=b[i]*b[i];b2+=b[i];
}
for(i=1;i<=n;i++){
A[i].x=A[i+n].x=a[i];
B[i].x=b[n-i+1];
}
while(limit<=(n*3)) limit<<=1,cnt++;
for(i=0;i<limit;i++) r[i]=((r[i>>1]>>1)|((i&1)<<(cnt-1)));
fft(A,1);fft(B,1);
for(i=0;i<=limit;i++) A[i]=A[i]*B[i];
fft(A,-1);
for(i=0;i<=limit;i++) A[i].x=(ll)(A[i].x/limit+0.5);
for(i=1;i<=n;i++){
for(j=-m;j<=m;j++){
ans=min(ans,a1+b1+j*j*n+2ll*j*(a2-b2)-2ll*(ll)A[i+n].x);
}
}
printf("%lld",ans);
}
```