本文共 1749 字，大约阅读时间需要 5 分钟。
题目上要求一个循环卷积的最小值，直接破环成链然后FFT就可以了。
然后考虑计算的式子，可以分成两个部分分开计算。
前半部分FFT，后半部分扫一遍。
#include #include #include #include #include #include #include #include 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-6 struct 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 >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