hihocoder1388 2016北京网络赛F题

题目在这里>_<

题意

求 $min\lbrace \sum\limits_{i=0}^{n-1}(A_i-B_{i+k})^2 \rbrace$ , 其中 $k=0,1, \dots n-1$.

思路

将原式展开后，只需求$min\lbrace \sum\limits_{i=0}^{n-1}(A_iB_{i+k}) \rbrace$，其它项为常数。
我们只需将$B$倒过来就变成了卷积的形式。令$C=A*B$，那么$C_i+C_{i+n}$便是将原来$B$中的元素旋转$n-1-i$次后的值。只需找出其最大值即可。
由于此题卡精度，所以需要先求出使答案最小的这个循环节，再带入原来的$A,B$数组求出答案。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Nmax=1e6+7;
const long double PI=acos(-1.0);
struct FFT 
{
    complex<long double> omega[Nmax],omegaInv[Nmax];
    void init(int n) 
    {
        for(int i=0;i<n;i++) 
        {
            omega[i]=complex<long double>(cos(2.0*PI*i/n),sin(2.0*PI*i/n));
            omegaInv[i]=conj(omega[i]);
        }
    }

    void transform(complex<long double> *a,int n,complex<long double> *omega) 
    {
        int k=1;
        while( (1<<k)<n ) 
            k++;
        for(int i=0;i<n;i++) 
        {
            int t=0;
            for(int j=0;j<k;j++) 
                if((i>>j)&1) 
                    t|=(1<<(k-j-1));
            if(i<t)
                swap(a[i],a[t]);
        }

        for(int l=2;l<=n;l<<=1) 
        {
            int m=l>>1,k=n/l;
            for(complex<long double> *p=a;p!=a+n;p+=l) 
            {
                for(int i=0;i<m;i++) 
                {
                    complex<long double> t=omega[k*i]*p[m+i];
                    p[m+i]=p[i]-t;
                    p[i]+=t;
                }
            }
        }
    }

    void dft(complex<long double> *a,int n) 
    {
        transform(a,n,omega);
    }

    void idft(complex<long double> *a,int n) 
    {
        transform(a,n,omegaInv);
        for(int i=0;i<n;i++) 
            a[i]/=n;
    }
    complex<long double> c1[Nmax],c2[Nmax];
    void multiply(ll *a1,int n1,ll *a2,int n2,ll *res) 
    {
         int n=1;
         while(n<n1+n2)
             n<<=1;
         for(int i=0;i<n;i++)//不要忘记初始化
         {
             c1[i].real(0.0);
             c1[i].imag(0.0);
             c2[i].real(0.0);
             c2[i].imag(0.0);
         }
         for(int i=0;i<n1;i++) 
             c1[i].real(a1[i]);
         for(int i=0;i<n2;i++) 
             c2[i].real(a2[n2-1-i]);
         init(n);
         dft(c1,n);
         dft(c2,n);
         for(int i=0;i<n;i++)
             c1[i]*=c2[i];
         idft(c1,n);
         for(int i=0;i<n;i++) 
             res[i]=(ll)(floor(c1[i].real()+0.5));
    }
}fft;
ll a[Nmax],b[Nmax],c[Nmax];
int main()
{
    int t,n;
    //freopen("1388.in","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        ll suma=0LL,sumb=0LL;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            suma+=a[i]*a[i];
        }
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&b[i]);
            sumb+=b[i]*b[i];
        }
        fft.multiply(a,n,b,n,c);
        ll ans=0LL;
        int k=0;
        for(int i=0;i<n;i++)
        {
            if(ans<c[i]+c[i+n])
            {
                ans=c[i]+c[i+n];
                k=n-1-i;
            }
        }
        ans=0LL;
        for(int i=0;i<n;i++)
            ans+=a[i]*b[(i+k)%n];
        printf("%lld\n",suma+sumb-2*ans);
    }
    return 0;
}