題目上要求一個循環卷積的最小值，直接破環成鏈然后FFT就可以了。

然后考慮計算的式子，可以分成兩個部分分開計算。

前半部分FFT，后半部分掃一遍。

#include <map> #include <ctime> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define ll long long #define double long double #define llinf 10000000000000000LL #define maxn 500005 #define eps 1e-6struct Complex{double x,y;Complex (){}Complex (double _x,double _y){x=_x;y=_y;}Complex operator + (Complex a) {return Complex(x+a.x,y+a.y);}Complex operator - (Complex a) {return Complex(x-a.x,y-a.y);}Complex operator * (Complex a) {return Complex(x*a.x-y*a.y,x*a.y+y*a.x);} }A[maxn],B[maxn];const double pi=acos(-1.0); int rev[maxn]; ll ans=llinf,res[maxn],sumA2=0,sumB2=0,sumA=0,sumB=0;void FFT(Complex *x,int n,int flag) {F(i,0,n-1) if (rev[i]>i) swap(x[rev[i]],x[i]);for (int m=2;m<=n;m<<=1){Complex wn=Complex(cos(2*pi/m),flag*sin(2*pi/m));for (int i=0;i<n;i+=m){Complex w=Complex(1.0,0);for (int j=0;j<(m>>1);++j){Complex u=x[i+j],v=x[i+j+(m>>1)]*w;x[i+j]=u+v;x[i+j+(m>>1)]=u-v;w=w*wn;}}} }int n,m,L=0;int main() {scanf("%d%d",&n,&m);F(i,0,n-1){int x;scanf("%d",&x);A[i].x=x;sumA+=x;sumA2+=(ll)x*x;}D(i,n-1,0){int x;scanf("%d",&x);B[i].x=x;sumB+=x;sumB2+=(ll)x*x;B[i+n].x=B[i].x;}for(m=1;m<=4*n;m<<=1);while(!(m>>L&1))L++;F(i,0,m-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));FFT(A,m,1);FFT(B,m,1);F(i,0,m-1)A[i]=A[i]*B[i];FFT(A,m,-1);F(i,0,m-1) res[i]=(A[i].x+0.4)/m;F(i,-100,100){ll tmp=2*i*(sumA-sumB)+n*i*i;F(j,n-1,2*n-1) ans=min(ans,sumA2+sumB2+tmp);}ll tmp=-llinf;F(i,n-1,2*n-1) tmp=max(tmp,res[i]);ans-=2*tmp;printf("%lld\n",ans); }

　　

轉載于:https://www.cnblogs.com/SfailSth/p/6813479.html

總結

以上是生活随笔為你收集整理的BZOJ 4827 [Hnoi2017]礼物 ——FFT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。