寒假学习计划

题意

给出两个数组x和y.可以选择一个数组,把其中每一位加上一个整数;每个数组都是首尾相接的,可以选择一个数组,然后把它旋转一定的角度.

最后要使\sum_{i=1}^{n}(x_{i}-y_{i})^2最小.求最小值是多少.

LOJ2020

BZOJ4827

题解

设给第二个数组每一位加了c.化简上面的式子可得:

\sum_{i=1}^{n}(x_{i}-y_{i})^2=\sum(x_{i}^2+y_{i}^2)+nc^2+2c\sum(y_{i}-x_{i})-2\sum_{i=1}^{n}x_{i}y_{i}

上式是关于c的二次函数,与数组是否旋转无关.问题在于如何求最后一项的最小值.

有个技巧是把一个数组重复一遍,另一个数组翻转,再在最后补上等量的0.然后计算卷积.假如数组长度为n的话,最后卷积结果的第n+1位到2n位就是旋转了各个角度的情况下的乘积之和.取最大值代入即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 480010
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;

int n,m,len,i;
LL c,Ans,sum,t;
LL a[N],b[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(LL &a,LL &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL LL Max(LL a,LL b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Ready(){
    reg int i=0;
    Ans=0;  sum=0;
    for (i=0;i<=n;i++)  Ans+=a[i]*a[i]+b[i]*b[i];
    for (i=0;i<=n;i++)  sum+=a[i]-b[i];
    c=round((double)sum/(n+1));
    Ans+=(LL)(n+1)*c*c; Ans-=2*c*sum;
    for (i=0;i<=n;i++)  b[n+i+1]=b[i];
    for (i=0;i<=n/2;i++)
        if (i!=n-i)
            Swap(a[i],a[n-i]);
    n=n*2+1;
}

inline LL Mi(LL x,LL y){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}

inline void Rader(LL y[]){
    int i=0,j=0,k=0;
    for (i=1,j=len>>1;i<len-1;i++){
        if (i<j)    Swap(y[i],y[j]);
        k=len>>1;
        while (j>=k)    j-=k,k>>=1;
        if (j<k)    j+=k;
    }
}

inline void NTT(LL a[],int f){
    int i=0,j=0,k=0;
    LL wn=0,w=0,u=0,t=0;
    Rader(a);
    for (k=2;k<=len;k<<=1){
        wn=Mi(3,(MOD-1)/k);
        if (f==-1)  wn=Mi(wn,MOD-2);
        for (i=0;i<len;i+=k){
            w=1;
            for (j=i;j<i+k/2;j++){
                u=a[j]; t=(w*a[j+k/2])%MOD;
                a[j]=(u+t)%MOD; a[j+k/2]=(u-t+MOD)%MOD;
                w=(w*wn)%MOD;
            }
        }
    }
    if (f==-1)
        for (i=0;i<len;i++) a[i]=(a[i]*Mi(len,MOD-2))%MOD;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();   n--;
    for (i=0;i<=n;i++)  a[i]=read();
    for (i=0;i<=n;i++)  b[i]=read();
    Ready();
    for (len=1;len<=n*2;len<<=1);
    NTT(a,1);   NTT(b,1);
    for (i=0;i<len;i++) a[i]=(a[i]*b[i])%MOD;
    NTT(a,-1);
    for (i=n/2+1;i<=n-1;i++)    t=Max(t,a[i]);
    Ans-=2*t;
    cout<<Ans<<endl;
    return 0;
}