【题解】[AH2017/HNOI2017] 礼物 FFT luoguP3723/bzoj4827 —Qiuly

~~题目背景有些……………~~
通过题目我们可以知道最终我们要求的式子就是：

$\sum_{i=1}^{n}(a_i+c-b_i)^2$
于是我们将式子拆开：

$(a_i+c-b_i)^2=a_i^2+b_i^2+c^2+2a_ic-2b_ic-2a_ib_i$

$\sum_{i=1}^{n}(a_i+c-b_i)^2=\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}b_i^2+nc^2+2c(\sum_{i=1}^{n}a_i-\sum_{i=1}^{n}b_i)-2\sum_{i=1}^{n}a_ib_i$
前面的这些都很容易求出，但是最后的

$\sum_{i=1}^{n}a_ib_i$ 无法很快算出，我们算答案的时候枚举

$c$ 以及手环旋转了多少，这个时候如果在里面直接大力计算

$\sum_{i=1}^{n}a_ib_i$ 可以拿到

$30$ 分。如果将这个式子在之前拿出来预处理一下，将会拿到

$70$ 分。

这个时候将 $a_i$ 反向，式子变为： $\sum_{i=1}^{n}a_{n-i+1}b_i$ ，可以发现这是一个卷积，是可以用 $FFT$ 跑的，众所周知 $FFT$ 的复杂度是 $O(nlogn)$ ，是能跑过的。

具体实现的时候我们需要将 $a$ 拉成两倍长，或者说是断环为链？至于为什么的话，是因为题目要求了这个数列是可以旋转的。然后按照上式将 $b$ 反向就好了。

Code:

#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>

#define PI 3.1415926535898
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
typedef long long ll;

const int N=5e5+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
} 

struct complex{complex(double a=0,double b=0){x=a,y=b;}double x,y;};
complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

int n,m,limit=1,a[N],b[N],filp[N];
ll a1=0,a2=0,b1=0,b2=0;
complex A[N],B[N];

inline void FFT(complex *f,short inv){
    for(int i=0;i<limit;++i)
        if(i<filp[i]){complex tmp=f[i];f[i]=f[filp[i]];f[filp[i]]=tmp;}
    for(int p=2;p<=limit;p<<=1){
        int len=p/2;
        complex tmp=complex(cos(PI/len),inv*sin(PI/len));
        for(int k=0;k<limit;k+=p){
            complex buf=complex(1,0);
            for(int l=k;l<k+len;++l){
                complex t=buf*f[len+l];
                f[len+l]=f[l]-t,f[l]=f[l]+t,buf=buf*tmp;    
            }
        }
    }return;
}

int main(){
    IN(n),IN(m);
    for(int i=1;i<=n;++i)
        IN(a[i]),a1+=a[i]*a[i],a2+=a[i];
    for(int i=1;i<=n;++i)
        IN(b[i]),b1+=b[i]*b[i],b2+=b[i];
    for(int i=1;i<=n;++i)
        A[i].x=A[i+n].x=a[i],B[i]=b[n-i+1];
    while(limit<=(3*n))limit<<=1;
    for(int i=0;i<limit;++i)filp[i]=(filp[i>>1]>>1)|((i&1)?limit>>1:0);
    FFT(A,1),FFT(B,1);
    for(int i=0;i<=limit;++i)A[i]=A[i]*B[i];
    FFT(A,-1);
    for(int i=0;i<=limit;++i)A[i].x=(ll)(A[i].x/limit+0.5);
    ll ans=inf;
    for(int i=1;i<=n;++i)
        for(int j=-m;j<=m;++j)
            ans=min(ans,a1+b1+1ll*j*j*n+2ll*j*(a2-b2)-2ll*(ll)A[i+n].x);
    printf("%lld\n",ans);
    return 0;
}

【题解】[AH2017/HNOI2017] 礼物 FFT luoguP3723/bzoj4827 —Qiuly

于2019年3月14日2019年3月14日由Qiuly发布

Code:

Qiuly

0 条评论

发表回复取消回复

【题解】[AH2017/HNOI2017] 礼物 FFT luoguP3723/bzoj4827 —Qiuly

于2019年3月14日2019年3月14日由Qiuly发布

Code:

Qiuly

0 条评论

发表回复 取消回复

发表回复取消回复