Bzoj4827--Hnoi2017礼物

Description

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

个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突

然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有

装饰物的亮度增加一个相同的自然数 c（即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，

但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差

异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n，

其中 n 为每个手环的装饰物个数，第 1 个手环的 i 号位置装饰物亮度为 xi，第 2 个手环的 i 号位置装饰物

亮度为 yi，两个手环之间的差异值为(参见输入输出样例和样例解释)： sum_{i=1}^{n}(x_i-y_i)^2麻烦你帮他

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

Input

输入数据的第一行有两个数n, m，代表每条手环的装饰物的数量为n，每个装饰物的初始亮度小于等于m。

接下来两行，每行各有n个数，分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

1≤n≤50000, 1≤m≤100, 1≤ai≤m

Output

输出一个数，表示两个手环能产生的最小差异值。

注意在将手环改造之后，装饰物的亮度可以大于 m。

-----------------------------------------------此后一千里----------------------------------------------

我们将平方打开，发现目的就是使$sum_limits_{i=1}{n} ai*bi$最大。

如果我们在一开始就找到这个最大的对应的话，之后再加上一个数，最大的对应还是这个对应。

然后我们把b数组翻转一下，发现是在求一个循环卷积，然后一发fft，之后枚举加的数乱搞就可以了。

代码：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-9
#define LL long long
using namespace std;

#define int LL
inline int Max(int a,int b) {return a>b?a:b;}
inline int Min(int a,int b) {return a<b?a:b;}
inline int Sqr(int a) {return a*a;}
inline int Abs(int a) {return a>0?a:-a;}
#undef int

#define MAXN 140000

int n,m,ans,all,dif,sum,sum2,ad;
int a[MAXN],b[MAXN],x1[MAXN],x2[MAXN];

namespace Untt{
    int MOD=998244353,g=10;
    
    LL Fpow(LL a,LL p) {
        LL ret=1,tmp=a;
        while(p) {
            if(p&1) ret=ret*tmp%MOD;
            tmp=tmp*tmp%MOD; p>>=1;
        }
        return ret;
    }
    
    int tra[140000];
    void NTT(int *a,int n,int p) {
        for(int i=1;i<n;i++) {
            tra[i]=tra[i>>1]>>1|(i&1 ? n>>1:0);
            if(tra[i]>i) swap(a[i],a[tra[i]]);
        }
        for(int i=1;i<n;i<<=1) {
            LL wn=Fpow(g,(MOD-1)/(i<<1)),w0,A,B;
            if(p) wn=Fpow(wn,MOD-2);
            for(int j=0;j<n;j+=i<<1) { 
                w0=1;
                for(int k=0;k<i;k++,w0=w0*wn%MOD) {
                    A=a[k+j];B=a[k+j+i];
                    a[k+j]=(A+w0*B)%MOD;
                    a[k+j+i]=((A-w0*B)%MOD+MOD)%MOD;
                }
            }
        }
        if(p) {
            LL rev=Fpow(n,MOD-2);
            for(int i=0;i<n;i++) a[i]=a[i]*rev%MOD;
        }
    }
}

int main() {
    dif=INF;
    scanf("%d%d",&n,&m);
    for(int i=n-1;~i;i--) scanf("%d",&b[i]);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) {
        x1[i]=a[i];x2[i]=b[n-i-1];
        sum+=a[i];sum2+=b[i];
    }
    if(sum2>sum) sum=sum2,ad=1;
    else ad=2;
    int len=1;
    while(len<n) len<<=1;len<<=1;
    Untt:: NTT(a,len,0);
    Untt:: NTT(b,len,0);
    for(int i=0;i<len;i++) a[i]=(LL) a[i]*b[i]%Untt:: MOD;
    Untt:: NTT(a,len,1);
    memset(b,0,sizeof(b));
    for(int i=0;i<len;i++) b[i%n]+=a[i];
    for(int i=0;i<n;i++) ans=Max(ans,b[i]);
    for(int i=0;i<=200;i++) {
        all=0;
        for(int j=0;j<n;j++) {
            if(ad==1) all+=Sqr(x1[j]+i);
            else all+=Sqr(x1[j]);
            if(ad==2) all+=Sqr(x2[j]+i);
            else all+=Sqr(x2[j]);
        }
        all=all-2*(ans+i*sum);
        dif=Min(dif,all);
    }
    printf("%d
",dif);
    return 0;
}

View Code