【HNOI2017】礼物-gift_综合

题面

??

解法

FFT：
??和式可化为：

$\sum i = 1 n (x i + c ? y i) 2 = \sum i = 1 n (x 2 i + y 2 i) + n ? c 2 ? 2 ? c ? \sum i = 1 n (y i ? x i) ? 2 ? \sum i = 1 n (x i ? y i)$ $\sum_{i=1}^{n}(x_i+c-y_i)^2= \sum_{i=1}^{n}(x_i^2+y_i^2)+n*c^2-2*c*\sum_{i=1}^{n}(y_i-x_i)-2*\sum_{i=1}^{n}(x_i*y_i)$
??当c确定时，前三项都为定值，为了使和式最小，只需要使得在旋转之后 $x_i*y_i$ 的和最大，即求旋转后的 $\sum_{i=1}^{n}(x_i*y_i)_{max}$
??* : c∈[-m,m]
??** : 求 $\sum_{i=1}^{n}(x_i*y_i)_{max}$ 只需利用FFT。假设旋转第一个环之后第一个环的第1个是原来第一个环的第k个，那么此时的 $\sum_{i=1}^{n}(x_i*y_i)$ 就为：
$\sum i = 1 n ? k + 1 (x k + i ? 1 ? y i) + \sum i = 1 k ? 1 (x i ? y n ? k + i + 1) \cdot \cdot \cdot \cdot \cdot \cdot ①$ $\sum_{i=1}^{n-k+1}(x_{k+i-1}*y_i)+\sum_{i=1}^{k-1}(x_i*y_{n-k+i+1}) ······①$
??如果把第一个环翻转，把环看作多项式，那么①式就是两个多项式乘积中一个系数的值，所以我们可以只翻转第一个环做一次FFT，然后只翻转第二个环做一次FFT，取两次结果中最大的系数就可以了

复杂度

O（ $nlogn+m$ ）

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define Rint register int
#define Lint long long int
using namespace std;
const double pi=acos(-1);
const int INF=0x3f3f3f3f;
const int N=150010;
struct complex  
{  double r,i;complex operator + (const complex o){  return (complex){ r+o.r,i+o.i };}complex operator - (const complex o){  return (complex){ r-o.r,i-o.i };}complex operator * (const complex o){  return (complex){ r*o.r-i*o.i,r*o.i+i*o.r };}
}f[N],g[N],s[N];
int a[N],b[N],w[N],v[N];
int n,m,ans,mx,N1;
void FFT(complex a[N],int n,int m,int opt)
{for(int i=1,j=0;i<n;i++){for(int k=n;j^=k>>=1,~j&k;)   ;if( i<j )   swap( a[i],a[j] );}complex wn,w,tmp;for(int d=0;(1<<d)<n;d++){int m=1<<d;wn=(complex){ cos(pi/m),sin(opt*pi/m) };for(int i=0;i<n;i+=m*2){w=(complex){ 1,0 };for(int j=0;j<m;j++,w=w*wn){tmp=w*a[i+j+m];a[i+j+m]=a[i+j]-tmp,a[i+j]=a[i+j]+tmp;}}}
}
void solve()
{if( !N1 )   for(N1=1;N1<=2*n;N1=N1*2)   ;FFT( f,N1,n,1 ),FFT( g,N1,n,1 );for(int i=0;i<=N1;i++)   s[i]=f[i]*g[i];FFT( s,N1,n,-1 );for(int i=0;i<=N1;i++)   f[i]=(complex){ 0,0 },g[i]=(complex){ 0,0 };
}
int main()
{freopen("gift.in","r",stdin);freopen("gift.out","w",stdout);int sum1,sum2,x;scanf("%d%d",&n,&m);sum1=sum2=0,ans=INF;for(int i=1;i<=n;i++)   scanf("%d",&a[i]),sum1+=a[i]*a[i];for(int i=1;i<=n;i++)   scanf("%d",&b[i]),sum1+=b[i]*b[i];for(int i=0;i<=n-1;i++)   f[i]=(complex){ a[n-i]*1.0,0 },g[i]=(complex){ b[i+1]*1.0,0 };solve();for(int i=1;i<=n;i++)   w[i]=(int)(s[n-i].r/N1+0.5);for(int i=0;i<=n-1;i++)   f[i]=(complex){ a[i+1]*1.0,0 },g[i]=(complex){ b[n-i]*1.0,0 };solve();for(int i=1;i<=n;i++)   v[i]=(int)(s[i-1].r/N1+0.5);for(int i=1;i<=n;i++)if( v[i-1]+w[i]>mx )   mx=v[i-1]+w[i],x=i;if( x>1 )//需要进行旋转{int tmp[N];for(int i=x;i<=n;i++)   tmp[i]=a[i];for(int i=n;i>=n-x+2;i--)   a[i]=a[i-n+x-1];for(int i=x;i<=n;i++)   a[i-x+1]=tmp[i];}for(int i=1;i<=n;i++)   sum2+=a[i]-b[i];if( sum2<0 )   sum2*=-1;for(int c=0;c<=m;c++)   ans=min( ans,sum1+n*c*c-2*c*sum2-2*mx );printf("%d\n",ans);return 0;
}