洛谷 P3723 [AH2017/HNOI2017]礼物 题解【FFT】【函数】

点击量：194

    卷积轻松想出来了但是挂在了别的推导上。

这个题也是HBOI2017啊

目录

题目描述

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

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

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

\[\sum_{i=1}^{n} (x_i-y_i)^2\]

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

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

输出样例#1：

1

说明

【样例解释】

需要将第一个手环的亮度增加\(1\)，第一个手环的亮度变为：\(2\ 3\ 4\ 5\ 6\)；

旋转一下第二个手环。对于该样例，是将第二个手环的亮度\(6\ 3\ 3\ 4\ 5\)向左循环移动一个位置，使得第二手环的最终的亮度为：\(3\ 3\ 4\ 5\ 6\)。

此时两个手环的亮度差异值为\(1\)。

【数据范围】

\(30\%\)的数据满足\(n\le 500, m\le 10\)；

\(70\%\)的数据满足\(n\le 5000\)；

\(100\%\)的数据满足\(1\le n\le 50000, 1\le m\le 100, 1\le a_i\le m\)。

题解：

    先不考虑改变数值，假定在数值上已经是最优，把原式展开，得到\(\sum_{i=1}^nx_i^2+\sum_{i=1}^ny_i^2-2x_iy_i\)。

    因为\(\sum_{i=1}^n x_i^2\),\(\sum_{i=1}^ny_i^2\)都是定值，我们要求出重新匹配后\(\sum_{i=1}^n x_iy_i\)的最小值，也可以认为是旋转了\(k\)个单位后，\(\sum_{i=1}^n x_iy_{i+k\pmod n}\)的最小值。

    在有一定FFT经验后，可以把上面的下标转化为卷积的形式。我们只需要把\(\{y_i\}\)数组调转过来，便成了\(\sum_{i=1}^n x_iy_{n-(i+k)+1\pmod n}\)，乘积项的下标之和总为\(n+k+1\)。此时我们直接把\(\{a_1,a_2,\dots,a_n\}\)和\(\{b_n,b_{n-1},\dots,b_1\}\)乘起来，旋转\(k\)个单位（\(k\in[1,n]\)）所得到的就是指数为\(n+k\pmod n\)的项的系数。这里答案既可能出现在\(k\)，也可能出现在\(n+k\)处，因为两个\(n\)次多项式相乘，所得到的最高次数为\(2n\)。核心是把\(b\)数组倒转过来。

    接着看数值改变的问题，假设对\(\{a_n\}\)数组整体加上\(c\)。因为要求匹配位置上的差值尽可能小，所以\(c\)可以是任意整数。当\(c\ge 0\)时，意义是对\(\{a_n\}\)数组整体加；当\(c<0\)时，意义是对\(\{b_n\}\)数组整体加，也可以理解为对\(\{a_n\}\)数组整体减。此时原式\(=\sum_{i=1}^{n} (x_i-y_i+c)^2\)。\(c\in \mathbb{Z}\)只是一个变化参量，根据正负不同其具体意义不同。

我推导的时候就是做到这，之后就没有思路了，因为当时感觉又是\(x_i,y_i\)又是\(c\)的，有3个“变量”，就没敢朝下写。

    这时尝试展开这个式子，因为我们要求一个\(c\)使得原式最小，需要把这个\(c\)确定下来。

\[\begin{align*}
\sum_{i=1}^n(x_i-y_i+c)^2&=\sum_{i=1}^n(x_i+c)^2+\sum_{i=1}^ny_i^2-\sum_{i=1}^n2(x_i+c)y_i\\
&=\sum_{i=1}^nx_i+\sum_{i=1}^n2x_ic+nc^2+\sum_{i=1}^ny_i^2-\sum_{i=1}^n2x_iy_i-\sum_{i=1}^n2y_ic\\
&=nc^2+2\sum_{i=1}^n(x_i-y_i)c+\sum_{i=1}^nx_i^2-\sum_{i=1}^n2x_iy_i+\sum_{i=1}^ny_i^2\\
&=nc^2+2\sum_{i=1}^n(x_i-y_i)c+\sum_{i=1}^n(x_i-y_i)^2
\end{align*}\]

    可以发现，这是一个关于\(c\)的二次函数。当\(c\)取离对称轴最近的整数时，原式有最小值。

    接着就只需要把\(\{a_n\}\)统一加上\(c\)（无论正负）就可以了。

    接着回到上面做FFT，取最小值，这道题就做完了。

Code：

#include<cstdio>
#include<cstring>
#include<cmath>
const double pi=acos(-1);
struct cpl
{
    double x,y;
    cpl(double x,double y)
    {
        this->x=x;
        this->y=y;
    }
    cpl(){x=y=0.0;}
    friend cpl operator +(cpl a,cpl b)
    {return cpl(a.x+b.x,a.y+b.y);}
    friend cpl operator -(cpl a,cpl b)
    {return cpl(a.x-b.x,a.y-b.y);}
    friend cpl operator *(cpl a,cpl b)
    {return cpl(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
}fft1[1<<17],fft2[1<<17],omg[1<<17],inv[1<<17];
int len,tot,pos[1<<17];
void init()
{
    for(int i=1;i<tot;++i)
        pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));
    for(int i=0;i<tot;++i)
    {
        omg[i]=cpl(cos(2*pi*i/tot),sin(2*pi*i/tot));
        inv[i]=cpl(omg[i].x,-omg[i].y);
    }
}
void fft(cpl f[],bool flag)
{
    for(int i=1;i<tot;++i)
        if(pos[i]>i)
        {
            cpl tmp=f[i];
            f[i]=f[pos[i]];
            f[pos[i]]=tmp;
        }
    for(int bs=1;bs<=len;++bs)
    {
        int r=(1<<bs),g=(1<<(bs-1));
        for(int i=0;i<tot;i+=r)
            for(int j=0;j<g;++j)
            {
                cpl t1=f[i+j],t2;
                if(flag)
                    t2=omg[j*(1<<(len-bs))]*f[i+j+g];
                else
                    t2=inv[j*(1<<(len-bs))]*f[i+j+g];
                f[i+j]=t1+t2;
                f[i+j+g]=t1-t2;
            }
    }
}
int a[1<<17],b[50010];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while((1<<len)<=2*n)
        ++len;
    tot=(1<<len);
    init();
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    int c=0;

    for(int i=1;i<=n;++i)
        c+=b[i]-a[i];
    if(c>=0)
        c=(int)((double)c/n+.5);
    else
        c=(int)((double)c/n-.5);
    long long sum=0;
    for(int i=1;i<=n;++i)
    {
        a[i]+=c;
        sum+=a[i]*a[i]+b[i]*b[i];
    }
    for(int i=1;i<=n;++i)
        fft1[i].x=a[i];
    for(int i=1;i<=n;++i)
        fft2[i].x=b[n-i+1];
    fft(fft1,1);
    fft(fft2,1);
    for(int i=0;i<tot;++i)
        fft1[i]=fft1[i]*fft2[i];
    fft(fft1,0);
    for(int i=0;i<tot;++i)
        a[i]=(int)(fft1[i].x/tot+.5);
    long long ans=0;
    for(int i=1;i<=n;++i)
        ans=ans>(a[i]+a[i+n])?ans:(a[i]+a[i+n]);
    printf("%lld\n",sum-2*ans);
    return 0;
}