「题解」「AHOI/HNOI2017」礼物 gift

$\texttt{FFT}$ 简单题。

题目链接:Luogu P3723/BZOJ/LibreOJ 2020/AHOI&HNOI2017 D1T3。

题目

题目描述

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 $n$ 个装饰物,并且每个装饰物都有一定的亮度。

但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的整数 $c$(可能是负数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 $1,2,\cdots,n$,其中 $n$ 为每个手环的装饰物个数,第一个手环的 $i$ 号位置装饰物亮度为 $x _ i$,第二个手环的 $i$ 号位置装饰物亮度为 $y _ i$,两个手环之间的差异值为(参见输入输出样例和样例解释):

$$\sum _ {i=1}^n(x _ i-y _ i)^2$$

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

数据范围

变量数据范围
$n$$1\leq n\leq 5\times 10^4$
$m$$1\leq m\leq 100$
$a _ i$$1\leq a _ i\leq m$

题解

思路

$$
\begin{aligned}
\texttt{ans}&=\sum _ {i=1}^n((x _ i+c _ 1)-(y _ i+c _ 2))^2\\
&=\sum _ {i=1}^n(x _ i+\delta-y _ i)^2\\
&=\sum _ {i=1}^n(x^2 _ i +\delta^2+y^2 _ i+2x _ i\delta-2y _ i\delta-2x _ iy _ i)\\
&=\sum x^2+\sum y^2+n\delta^2+2\delta\sum(x-y)-2\sum a _ ib _ i
\end{aligned}
$$

所以我们需要最大化 $\sum a _ ib _ i$,这个很简单。

考虑设 $c _ i=b _ {n-i+1}$ ,那么我们只要最大化 $\sum a _ ic _ {n-i+1}$,考虑到转动的问题,我们其实只要把 $a$ 复制一遍即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=50000+5;
const int MAXSIZE=131072*8;
const double pi=acos(-1.0);

struct Complex{ //复数
    double x,y;
    inline Complex(reg double x=0,reg double y=0):x(x),y(y){
        return;
    }
    inline Complex operator+(const Complex& a){ //加法
        return Complex(x+a.x,y+a.y);
    }
    inline Complex operator-(const Complex& a){ //减法
        return Complex(x-a.x,y-a.y);
    }
    inline Complex operator*(const Complex& a){ //乘法
        return Complex(x*a.x-y*a.y,x*a.y+a.x*y);
    }
};

int limit;
int r[MAXSIZE]; //翻转数组

inline void FFT(reg Complex a[],reg int f){
    for(reg int i=0;i<limit;++i)
        if(i<r[i])
            swap(a[i],a[r[i]]); //翻转
    for(reg int i=1;i<limit;i<<=1){
        Complex w(cos(pi/i),f*sin(pi/i));
        for(reg int j=0;j<limit;j+=(i<<1)){
            Complex e(1,0);
            for(reg int k=0;k<i;++k,e=e*w){
                static Complex x,y;
                x=a[j+k],y=a[j+k+i]*e;
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if(f==-1)
        for(reg int i=0;i<limit;++i)
            a[i].x/=1.0*limit;
    return;
}

int n,m;
int a[MAXN],b[MAXN];
Complex A[MAXSIZE],B[MAXSIZE];

int main(void){
    n=read(),m=read();
    for(reg int i=1;i<=n;++i)
        a[i]=read();
    for(reg int i=1;i<=n;++i)
        b[i]=read();
    reg ll sum1=0,sum2=0; //sum1 是 a-b,sum2 是 a^2+b^2
    for(reg int i=1;i<=n;++i){
        sum1+=a[i]-b[i];
        sum2+=a[i]*a[i]+b[i]*b[i];
    }
    for(reg int i=1;i<=n;++i)
        A[i].x=A[i+n].x=a[i]; //复制
    for(reg int i=1;i<=n;++i)
        B[n-i+1].x=b[i]; //翻转
    limit=1;
    reg int l=0;
    while(limit<=3*n)
        limit<<=1,++l;
    for(reg int i=0;i<limit;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(A,1),FFT(B,1);
    for(reg int i=0;i<limit;++i)
        A[i]=A[i]*B[i]; //卷积
    FFT(A,-1);
    ll ans=1e18;
    for(reg int i=1;i<=n;++i)
        for(reg int j=-m;j<=m;++j)
            ans=min(ans,sum2+1ll*n*j*j-2ll*j*sum1-2ll*(ll)(A[i+n].x+0.5)); //求最小值
    printf("%lld\n",ans); //输出
    return 0;
}