洛谷P3723 [AH2017/HNOI2017]礼物（FFT）

传送门

首先，两个数同时增加自然数值相当于只有其中一个数增加（此增加量可以小于0）

我们令$x$为当前的增加量，${a},{b}$分别为旋转后的两个数列，那么$$ans=\sum_{i=1}^n(a_i+x-b_i)^2$$

然后把第$i$项提出来并展开，可得$$(a_i+x-b_i)^2=a_i^2+b_i^2+x^2+2xa_i-2xb_i-2a_ib_i$$

那么答案就是$$ans=\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2+nx^2+2x(\sum_{i=1}^na_i+\sum_{i=1}^nb_i)-2\sum_{i=1}^na_ib_i$$

然后发现，答案里面只有最后一项与$a,b$的顺序有关（也就是旋转成了什么样子），前面的项都是常数（对同一个$x$来说），那么我们只要令$\sum_{i=1}^na_ib_i$最大就能让答案最小了

我们考虑一下，如果把数列$b$给反过来，那么最后一项就变成了$\sum_{i=1}^na_ib_{n-i+1}$，这是一个卷积的形式，可以直接用FFT计算1$项的系数）

那么我们把数列$b$反过来，然后把数列$a$倍长，那么两式卷积之后第$n+1$到第$2n$项里面最大值就是最大的$\sum_{i=1}^na_ib_i$

于是只要枚举一下$x$和旋转（多项式的第几项）就好了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #define ll long long

 #define inf 0x3f3f3f3f3f3f3f3f

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;const double Pi=acos(-1.0);

 struct complex{

     double x,y;

     complex(double xx=,double yy=){x=xx,y=yy;}

     inline complex operator +(complex b){return complex(x+b.x,y+b.y);}

     inline complex operator -(complex b){return complex(x-b.x,y-b.y);}

     inline complex operator *(complex b){return complex(x*b.x-y*b.y,x*b.y+y*b.x);}

 }A[N],B[N];

 int n,m,l,r[N],limit=,a[N],b[N];ll a1,a2,b1,b2,ans=inf;

 void FFT(complex *A,int type){

     for(int i=;i<limit;++i)

     if(i<r[i]) swap(A[i],A[r[i]]);

     for(int mid=;mid<limit;mid<<=){

         complex Wn(cos(Pi/mid),type*sin(Pi/mid));

         for(int R=mid<<,j=;j<limit;j+=R){

             complex w(,);

             for(int k=;k<mid;++k,w=w*Wn){

                 complex x=A[j+k],y=w*A[j+mid+k];

                 A[j+k]=x+y,A[j+mid+k]=x-y;

             }

         }

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read();

     for(int i=;i<=n;++i)

     a[i]=read(),a1+=a[i]*a[i],a2+=a[i];

     for(int i=;i<=n;++i)

     b[i]=read(),b1+=b[i]*b[i],b2+=b[i];

     for(int i=;i<=n;++i)

     A[i].x=A[i+n].x=a[i],B[i].x=b[n-i+];

     while(limit<=(n*)) limit<<=,++l;

     for(int i=;i<limit;++i)

     r[i]=(r[i>>]>>)|((i&)<<(l-));

     FFT(A,),FFT(B,);

     for(int i=;i<limit;++i) A[i]=A[i]*B[i];

     FFT(A,-);

     for(int i=;i<limit;++i) A[i].x=(ll)(A[i].x/limit+0.5);

     for(int i=;i<=n;++i)

     for(int j=-m;j<=m;++j)

     cmin(ans,a1+b1+j*j*n+2ll*j*(a2-b2)-2ll*(ll)A[n+i].x);

     printf("%lld\n",ans);

     return ;

 }

巴特西

洛谷P3723 [AH2017/HNOI2017]礼物（FFT）

最新文章

热门文章