P3723 [AH2017/HNOI2017]礼物(构造FFT)

传送门

最小化

$\sum\limits_{i=1}^n(a_i-b_i)^2$

同时增大亮度是没有意义的,可以转化为增大一个数组的亮度,设增大了数组 $a$ 亮度 $x$

$\sum\limits_{i=1}^n(a_i-b_i+x)^2$

$=\sum\limits_{i=1}^n a_i+\sum\limits_{i=1}^nb_i^2+nx^2+2x\sum\limits_{i=1}^n(a_i-b_i)-2\sum\limits_{i=1}^na_ib_i$

假设增加的亮度一定,变化的就只有最后一项,也就是最大化 $2\sum\limits_{i=1}^na_ib_i$

但是每一种对齐方式都需要计算形如

$-2(a_1b_x+a_2b_{x+1}...+a_{n}b_{x-1})$

的式子

这部分已经是 $O(n)$ 的了

但是如果把 $a$ 数组复制一份在最后面是一个长度 $2n$ 的序列

把数组 $b$ 反转,做卷积得到的 $k\in[n+1,2n]$ 项中有

$c_k=\sum\limits_{i+j==k}a_ib_j$

模拟一下 $k=n+2$ 的情况

数组 $a_1\ a_2\ ...a_n\ a_1\ a_2\ ...a_n$ 和 $b_n\ b_{n-1}....b_1$ 卷积

$c_{n+2}=a_2*b_1+a_3*b_2+a_4*b_3...a_1*b_{n-1}$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6+10;
const int mod = 998244353,G=3,Gi=(mod+1)/3;
int n,m,r[maxn],a[maxn],b[maxn];
int quick(int x,int n)
{
    int ans = 1;
    for( ; n ; n>>=1,x=x*x%mod )
        if( n&1 )    ans = ans*x%mod;
    return ans; 
}
void init(int limit)
{
    for(int i=0;i<limit;i++)    r[i] = ( r[i>>1]>>1 ) | ( (i&1)?limit>>1:0 );
}
void NTT(int *a,int limit,int type )
{
    for(int i=0;i<limit;i++)
        if( i<r[i] )    swap( a[i],a[r[i]] );
    for(int mid=1;mid<limit;mid<<=1 )
    {
        int wn = quick( (type==1)?G:Gi,(mod-1)/(mid<<1));
        for(int R=mid<<1,i=0;i<limit;i+=R)
        for(int w=1,k=0;k<mid;k++,w=w*wn%mod )
        {
            int x = a[i+k], y = a[i+k+mid]*w%mod;
            a[i+k] = (x+y)%mod, a[i+k+mid] = (x-y+mod)%mod;
        }
    }
    if( type==1 )    return;
    int inv = quick(limit,mod-2);
    for(int i=0;i<limit;i++)    a[i] = a[i]*inv%mod;
}
void mul(int *a,int *b,int n,int m)
{
    int limit = 1;
    while( limit<=n+m )    limit<<=1;
    init(limit);
    for(int i=0;i<limit;i++)
    {
        if( i>n )    a[i] = 0;
        if( i>m )    b[i] = 0;
    }
    NTT(a,limit,1); NTT(b,limit,1);
    for(int i=0;i<limit;i++)    a[i] = a[i]*b[i]%mod;
    NTT(a,limit,-1);
}
int prea,preb,ajb,ans=1e9;
signed main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        a[i+n] = a[i];
    }
    for(int i=1;i<=n;i++)    { cin >> b[i]; }
    for(int i=1;i<=n;i++)
        prea+=a[i]*a[i],preb+=b[i]*b[i],ajb+=a[i]-b[i];
    for(int l=1,r=n;r>=l;r--,l++)    swap( b[l],b[r] );
    mul(a,b,2*n,n);
    for(int i=-100;i<=100;i++)//给i加上这么多
    for(int j=n+1;j<=2*n;j++)
        ans = min( ans,prea+preb+ajb*2*i+n*i*i-2*a[j] );    
    cout << ans;
}