Loading...

洛谷P3723 [AH2017/HNOI2017]礼物

check评论:0 条 remove_red_eye浏览量:943 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-16

推式子吧owo

我们假设给第一个环每个加$q$

原式$=\sum\limits_{i=1}^n (x_i^2+y_i^2+q^2-2x_iy_i+2x_iq-2y_iq)$

即$\sum (x_i^2+y_i^2)+nq^2-2q(\sum x_i-\sum y_i)-2\sum x_iy_i$

发现前面的都是定值,只需要最后一项最大即可

$\sum\limits_{i=1}^n x_iy_i$没法快速算,可以想到将$x_i$翻转,之后就是$\sum\limits_{i=1}^n x_{n-i+1}y_i$了,这是个卷积的形式,直接$NTT$即可

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353,ge=3;
#define int long long
int x[200010],y[200010],z[200010],limit=1,l,r[200010];
int ksm(int qaq,int f)
{
    int res=1;
    int flag=0;
    if(qaq==limit)
    {
        flag=1;
    }
    while(f)
    {
        if(f&1)
        {
            res=res*qaq%mod;
        }
        qaq=qaq*qaq%mod;
        f>>=1;
    }
    return res;
}
void NTT(int *n,int flag)
{
    for(int i=0;i<limit;i++)
    {
        if(i<r[i])
        {
            swap(n[i],n[r[i]]);
        }
    }
    for(int mid=1;mid<limit;mid<<=1)
    {
        int wn=ksm(ge,flag==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)));
        for(int r=(mid<<1),i=0;i<limit;i+=r)
        {
            int w=1;
            for(int k=0;k<mid;k++,w=w*wn%mod)
            {
                int m1=n[i+k],m2=w*n[i+mid+k]%mod;
                n[i+k]=(m1+m2)%mod,n[i+mid+k]=(m1-m2+mod)%mod;
            }
        }
    }
}
int ans1,ans2,sum1,sum2;
main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x[i]);
        ans1+=x[i]*x[i];
        sum1+=x[i];
    }    
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&y[i]);
        y[i+n]=y[i];
        ans2+=y[i]*y[i];
        sum2+=y[i];
    }
    sum1<<=1,sum2<<=1;
    reverse(x+1,x+n+1);
    while(limit<(n<<1)+1)
    {
        limit<<=1,l++;
    }
    for(int i=1;i<=limit;i++)
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    } 
    NTT(x,1),NTT(y,1);
    for(int i=0;i<=limit;i++)
    {
        z[i]=x[i]*y[i];
    }
    NTT(z,0);
    int inv=(ksm(limit,mod-2)+mod)%mod;;
    for(int i=0;i<=limit;i++)
    {
        z[i]=(mod+z[i]*inv)%mod;
    }
    int ans=0x3f3f3f3f;
    for(int i=-m;i<=m;i++)
    {
        for(int j=n;j<(n<<1);j++)
        {
            ans=min(ans,ans1+ans2+n*i*i+sum1*i-sum2*i-z[j]*2);
        }
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名