@zzzc18 2017-12-27T14:47:08.000000Z 字数 3700 阅读 1129

BZOJ4827: [Hnoi2017]礼物

bzoj FFT

由于之前FFT学习笔记实在太长了，就不再往里面加了

Description

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 $n$ 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数 $c$ （即非负整数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，
但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1,2,…,n$ ，其中 $n$ 为每个手环的装饰物个数，第 $1$ 个手环的 $i$ 号位置装饰物亮度为 $x_i$ ，第 $2$ 个手环的 $i$ 号位置装饰物
亮度为 $y_i$ ，两个手环之间的差异值为(参见输入输出样例和样例解释)： $\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$ 。

Sample Input

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

Sample Output

【样例解释】

需要将第一个手环的亮度增加1，第一个手环的亮度变为： 2 3 4 5 6 旋转一下第二个手环。对于该样例，是将第二个手环的亮度6 3 3 4 5向左循环移动 2017-04-15 第 6 页，共 6 页 一个位置，使得第二手环的最终的亮度为：3 3 4 5 6。此时两个手环的亮度差异值为1。

Solution:

我们根据题意，另第一个手环的增加量为 $c$ ，第二个手环旋转过 $t$ 个位置，最终在 $t$ 位置的差异值为函数 $G(t)$ 。

不难把题意写成一下式子：

$G(t)=\sum_{i=1}^{n}(a_i+c-b_{i+t})^2$

然后进行一些化简

$\begin{equation*} \begin{aligned} G(t)&=\sum_{i=1}^{n}(a_i+c-b_{i+t})^2\\ &=\sum_{i=1}^{n}[(a_i+c)^2-2(a_i+c)b_{i+t}+b^2_{i+t}]\\ &=\sum_{i=1}^{n}(a^2_i+2a_ic+c^2-2a_ib_{i+t}-2cb_{i+t}+b^2_{i+t})\\ &=\sum a^2_i + \sum b^2_{i+t} + nc^2 + 2c\sum(a_i-b_{i+t})-2\sum_{i=1}^{n}a_ib_{i+t} \end{aligned} \end{equation*}$

这时，我们可以发现，上式中的 $\sum a^2_i + \sum b^2_{i+t}$ 是一个定值，而对于各个 $t$ 的 $\sum_{i=1}^{n}a_ib_{i+t}$ 可以进行计算，而考虑到 $m$ 只有 $100$ ，可以枚举每一个 $c\in [0,m]$ 计算上式的值，并取最小值即为最终答案。

对于 $\sum_{i=1}^{n}a_ib_{i+t}$ 的计算，记 $f(t)=\sum_{i=1}^{n}a_ib_{i+t}$ ，

将 $a$ 反转得到 $a^R$ ，则 $f(t)=\sum_{i=1}^{n}a^R_{n-i+1}b_{i+t}$ ，

那么 $h(n+t+1)=f(t)=\sum_{i=1}^{n}a^R_{n-i+1}b_{i+t}$ ，这是一个卷积的形式，可以使用FFT进行优化，具体操作的时候只要在 $b$ 数组，后面复制一遍其本身，使长度达到 $2n$ 即可。

~~感觉m可以很大，不知道为什么只有100，可以直接暴力枚举~~

总时间复杂度为 $O(mnlogn)$

/**************************************************************
    Problem: 4827
    User: zzzc18
    Language: C++
    Result: Accepted
    Time:980 ms
    Memory:10980 kb
****************************************************************/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const double PI = acos(-1.0);
const int MAXN = 200000+9;
int n,m;
int loc[MAXN];
int size,bit_length;
struct C{
    double x,y;
    C(double _x=0,double _y=0):x(_x),y(_y){}
};
C operator + (const C &A,const C &B){
    return C(A.x+B.x,A.y+B.y);
}
C operator - (const C &A,const C &B){
    return C(A.x-B.x,A.y-B.y);
}
C operator * (const C &A,const C &B){
    return C(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
}
C A1[MAXN],B1[MAXN];
LL calc[MAXN];
LL sumA,sumB;
LL sumA2,sumB2;
int a[MAXN],b[MAXN];
void init(int len){
    for(size=1,bit_length=-1;size<len;size<<=1,bit_length++);
    int now=0;
    for(int i=0;i<size;i++){
        loc[i]=now;
        for(int j=1<<bit_length;(now^=j)<j;j>>=1);
    }
}
void DFT(int *A,C *re){
    for(int i=0;i<size;i++)
        re[i]=C(A[loc[i]],0);
    for(int k=2;k<=size;k<<=1){
        int len=k>>1;
        C Wn(cos(2.0*PI/k),sin(2.0*PI/k));
        for(int i=0;i<size;i+=k){
            C W(1,0);
            for(int j=0;j<len;j++){
                C u=re[i+j],v=re[i+j+len]*W;
                re[i+j]=u+v;
                re[i+j+len]=u-v;
                W=W*Wn;
            }
        }
    }
}
void IDFT(C *A,C *re){
    for(int i=0;i<size;i++)
        re[i]=A[loc[i]];
    for(int k=2;k<=size;k<<=1){
        int len=k>>1;
        C Wn(cos(2.0*PI/k),sin(-2.0*PI/k));
        for(int i=0;i<size;i+=k){
            C W(1,0);
            for(int j=0;j<len;j++){
                C u=re[i+j],v=re[i+j+len]*W;
                re[i+j]=u+v;
                re[i+j+len]=u-v;
                W=W*Wn;
            }
        }
    }
    for(int i=0;i<size;i++)
        re[i].x/=size;
}
void solve(){
    init(n<<1);
    DFT(a,A1);DFT(b,B1);
    for(int i=0;i<size;i++)
        A1[i]=A1[i]*B1[i];
    IDFT(A1,B1);
    for(int i=0;i<size;i++)
        calc[i]=-2LL*LL(B1[i].x+0.5);
    /*//DEBIG
      for(int i=0;i<size;i++)
      printf("%lld\n",calc[i]/(-2LL));*/
    LL ans=1000000000000000;
    for(int t=0;t<=n;t++){
        LL val=calc[n+t+1]+sumA2+sumB2;
        LL tmp=1000000000000000;
        for(int i=0;i<=m;i++)
            tmp=min(tmp,1LL*n*i*i+2LL*i*(sumA-sumB)+val);
        ans=min(ans,tmp);
    }
    printf("%lld\n",ans);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sumA+=a[i];
        sumA2+=a[i]*a[i];
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&i[b]);
        b[i+n]=b[i];
        sumB+=b[i];
        sumB2+=b[i]*b[i];
    }
    reverse(a+1,a+n+1);
    solve();
    return 0;
}