loj #2020. 「AHOI / HNOI2017」礼物

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有

但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $xix_ixi，第二个手环的 iii 号位置装饰物亮度为 yiy_iyi，两个手环之间的差异值为（参见输入输出样例和样例解释）：$

sum_{i = 1}^n (x_i - y_i)^2​i=1​∑​n​​(x​i​​−y​i​​)​2​​

麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

输入数据的第一行有两个数

输出一个数，表示两个手环能产生的最小差异值。注意在将手环改造之后，装饰物的亮度可以大于

样例输入

5 6
1 2 3 4 5
6 3 3 4 5

样例输出

样例解释

需要将第一个手环的亮度增加

此时两个手环的亮度差异值为

对于 $30%30\%30% 的数据，n≤500,m≤10nle 500, mle 10n≤500,m≤10；对于 70%70\%70% 的数据，n≤5000nle 5000n≤5000；对于 100%100\%100% 的数据，1≤n≤50000,1≤m≤100,1≤ai≤m1le nle 50000, 1le mle 100, 1le a_ile m1≤n≤50000,1≤m≤100,1≤ai≤m。$

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

我们令增加量为$x$，旋转以后的原数列为${a}{b}$那么现在的费用就是：

$sum_{i=1}^nleft(a_i+x-b_i ight)^2$

我们把第i项拿出来拆开，得到：

$left(a_i+x-b_i ight)^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+2xleft(sum_{i=1}^na_i-sum_{i=1}^nb_i ight)-2sum_{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$的最大值

然后把前面的不变项加上，就是答案了

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 50010
#define mod 1000000007
using namespace std;
int n,m,a[maxn],b[maxn];
long long ans=1000000000000000LL;
long long count(int s1,int s2){
    long long res=0;
    for(int i=0;i<n;i++)
        res+=1LL*(a[i+s1]-b[i+s2])*(a[i+s1]-b[i+s2]);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=1;i<=n;i++)scanf("%d",&b[i]),b[i+n]=b[i];
    for(int add=0;add<=m;add++){
        for(int i=1;i<=n+n;i++)a[i]+=add;
        for(int i=1;i<=n;i++)ans=min(ans,count(i,1));
        for(int i=1;i<=n+n;i++)a[i]-=add;
    }
    for(int add=0;add<=m;add++){
        for(int i=1;i<=n+n;i++)b[i]+=add;
        for(int i=1;i<=n;i++)ans=min(ans,count(1,i));
        for(int i=1;i<=n+n;i++)b[i]-=add;
    }
    cout<<ans;
    return 0;
}

30分暴力

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 400010
#define PI (acos(-1.0))
using namespace std;
int n,m,cnt=0,rd[maxn],a[maxn],b[maxn];
long long a1,a2,b1,b2,ans=1000000000000000LL;
struct node{
    double x,y;
    node(double a=0,double b=0):x(a),y(b){}
    node operator + (const node &c)
    {return node(x+c.x,y+c.y);}
    node operator - (const node &c)
    {return node(x-c.x,y-c.y);}
    node operator * (const node &c)
    {return node(x*c.x-y*c.y,x*c.y+y*c.x);}
    node operator / (const double &c)
    {return node(x/c,y/c);}
}A[maxn],B[maxn];
void fft(node *a,int N,int f){
    node wn,w;int i;
    for(int i=0;i<=N;i++)
        if(rd[i]>i)swap(a[i],a[rd[i]]);
    for(int k=1;k<N;k<<=1){
        wn=node(cos(PI/k),f*sin(PI/k));
        for(int j=0;j<N;j+=(k<<1)){
            for(w=node(1,0),i=0;i<k;i++,w=w*wn){
                node x=a[i+j];
                node y=a[i+j+k]*w;
                a[i+j]=x+y;
                a[i+j+k]=x-y;
            }
        }
    }
    if(f==-1)
        for(int i=0;i<=N;i++)a[i]=a[i]/N;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a1+=a[i]*a[i];a2+=a[i];
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        b1+=b[i]*b[i];b2+=b[i];
    }
    for(int i=1;i<=n;i++){
        A[i].x=A[i+n].x=a[i];
        B[i].x=b[n-i+1];
    }
    int N=1;while(N<=(n*3))N<<=1,cnt++;
    for(int i=0;i<=N;i++)rd[i]=(rd[i>>1]>>1)|((i&1)<<(cnt-1));
    fft(A,N,1);fft(B,N,1);
    for(int i=0;i<=N;i++)A[i]=A[i]*B[i];
    fft(A,N,-1);
    for(int i=0;i<=N;i++)A[i].x=(long long)(A[i].x+0.5);
    for(int i=1;i<=n;i++)
        for(int j=-m;j<=m;j++)
            ans=min(ans,a1+b1+1LL*j*j*n+2LL*j*(a2-b2)-2LL*(long long)A[i+n].x);
    cout<<ans;
    return 0;
}

100分 FFT