祎隋

AH2017/HNOI2017 礼物
链接题解:其实就是将A[i]翻转加倍,然后用循环卷积做个匹配即可,关于循环卷积,详见:code:#include&...
扫描右侧二维码阅读全文
04
2019/04

AH2017/HNOI2017 礼物

链接

题解:
其实就是将A[i]翻转加倍,然后用循环卷积做个匹配即可,关于循环卷积,详见:

code:

#include<bits/stdc++.h>
#define maxn 50005
typedef long long ll;
using namespace std;
int n,m;
int x[maxn],y[maxn],s,sx,sy,c;
const double pi=acos(-1.0);
struct cp{
    double x,y;//x实部y虚部 
    cp operator+(const cp &a){
        return (cp){x+a.x,y+a.y};
    } 
    cp operator-(const cp &a){
        return (cp){x-a.x,y-a.y};
    }
    cp operator*(const cp &a){
        return (cp){x*a.x-y*a.y,x*a.y+y*a.x};
    }
};
cp a[maxn*3*2],b[maxn*3*2];//内存经常有不够的情况
void change(cp y[],int len){
    for(int i=1,j=len/2;i<len-1;i++){
        if(i<j) swap(y[i],y[j]);
        int k=len>>1;
        while(j>=k){
            j-=k;
            k>>=1;
        }
        if(j<k) j+=k;
    } 
}
void fft(cp y[],int len,int on){
    change(y,len);
    for(int h=2;h<=len;h<<=1){
        cp base=(cp){cos(2*pi/h),sin(2*pi*on/h)};
        for(int j=0;j<len;j+=h){
            cp w=(cp){1,0};
            for(int k=j;k<j+h/2;k++){
                cp t1=y[k];
                cp t2=w*y[k+h/2];
                y[k]=t1+t2;
                y[k+h/2]=t1-t2;
                w=w*base;
            }
        }
    }
    if(on==-1){
        for(int i=0;i<len;i++) y[i].x/=len;
    }
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&x[i]);
        sx+=x[i]*x[i];
        s+=x[i];
    }
    for(int i=0;i<n;i++){
        scanf("%d",&y[i]);
        sy+=y[i]*y[i];
        s-=y[i];
    }
    //c=(ll)((-s/n)+0.5);
    int len=1;
    for(len;len<=(n<<1);len<<=1);//因为x串加倍 
    for(int i=0;i<2*n;i++) a[i]=(cp){x[i%n],0};
    for(int i=0;i<n;i++) b[i]=(cp){y[n-1-i],0};
    fft(a,len,1);
    fft(b,len,1);
    for(int i=0;i<len;i++) a[i]=a[i]*b[i];
    fft(a,len,-1);
    int ans=1000000000;
    for(int cc=-m;cc<=m;cc++)
    for(int i=n;i<2*n;i++){
        ans=min(ans,sx+sy+n*cc*cc+2*cc*s-2*(int)(a[i].x+0.5));
        //printf("%d\n",(int)a[i].x);
    }
    printf("%d",ans);
}
int main(){
    //freopen("in.txt","r",stdin);
    init();
    
    return 0;
}
Last modification:April 5th, 2019 at 08:13 am

Leave a Comment