题目
解法
考虑
[sum_{i=1}^n(x_i-y_i+c)^2
]
[=sum_{i=1}^nx_i^2+sum_{i=1}^ny_i^2+n imes c^2+2 imes c imes sum_{i=1}^nx_i-2 imes c imes sum_{i=1}^ny_i-2 imes sum_{i=1}^nx_iy_i
]
显然如果枚举 (c)，就只有最后一项是未知的。问题转化成 (maxleft{sum_{i=1}^nx_iy_i ight})。
有一步转化：将 (x) 序列翻转，那么即是求 (maxleft{sum_{i=1}^nx_{n-i+1}y_i ight})。
这是什么？卷积！容易发现答案就在第 (n+1) 项中。
但是我们的序列是可以旋转的，于是将 (x) 序列倍长，我们选 ([n+1,2n]) 中的最大值即为答案。
时间复杂度 (mathcal O(n imes m))。
代码
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
const double Pi=acos(-1.0);
int n,m,lim,bit,rev[maxn],a[maxn],b[maxn];
ll a1,a2,b1,b2,ans=1e15;
struct cp {
double x,y;
cp operator + (const cp t) {return (cp) {x+t.x,y+t.y};}
cp operator - (const cp t) {return (cp) {x-t.x,y-t.y};}
cp operator * (const cp t) {return (cp) {x*t.x-y*t.y,y*t.x+x*t.y};}
} tmp,w,wn,f[maxn],g[maxn];
void init() {
lim=1;
while(lim<=n*3) lim<<=1,++bit;
rep(i,0,lim-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
}
void FFT(cp *t,int op) {
rep(i,0,lim-1) if(i<rev[i]) swap(t[i],t[rev[i]]);
for(int mid=1;mid<lim;mid<<=1) {
wn=(cp) {cos(Pi/mid),sin(Pi/mid)*op};
for(int i=0;i<lim;i+=(mid<<1)) {
w=(cp) {1,0};
for(int j=0;j<mid;++j,w=w*wn) {
tmp=w*t[i+j+mid];
t[i+j+mid]=t[i+j]-tmp,t[i+j]=t[i+j]+tmp;
}
}
}
}
int main() {
n=read(9),m=read(9);
rep(i,1,n) {
a[i]=read(9);
a1+=a[i],a2+=a[i]*a[i];
}
rep(i,1,n) {
b[i]=read(9);
b1+=b[i],b2+=b[i]*b[i];
}
rep(i,0,n-1) f[i].x=f[i+n].x=a[i+1],g[i].x=b[n-i];
init();
FFT(f,1),FFT(g,1);
rep(i,0,lim-1) f[i]=f[i]*g[i];
FFT(f,-1);
rep(i,0,(n<<1)-1) f[i].x=(ll)(f[i].x/lim+0.5);
rep(i,0,n-1) rep(j,-m,m) ans=Min(ans,a2+b2+j*j*n+2ll*j*(a1-b1)-2ll*(ll)f[i+n].x);
print(ans,'
');
return 0;
}