题解 P3723 【[AH2017/HNOI2017]礼物】

· · 题解

广告

蒟蒻のblog

正文

首先，有一个结论：两个手环增加非负整数亮度，等于其中一个增加一个整数亮度（可以为负）

我们令增加量为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：

#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);
}