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

传送门

最小化

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

假设增加的亮度一定,变化的就只有最后一项,也就是最大化

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

的式子

这部分已经是的了

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

把数组反转,做卷积得到的项中有

模拟一下的情况

数组和卷积

#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;
}