首页 > 代码库 > hihoCoder 1388 Periodic Signal(FFT)
hihoCoder 1388 Periodic Signal(FFT)
【题目链接】 http://hihocoder.com/problemset/problem/1388
【题目大意】
给出A数列和B数列,求下图式子:
【题解】
我们将多项式拆开,我们可以得到固定项A2和B2,以及变动项-2AB,所以现在只要最大化AB即可。我们发现将A序列倒置,B序列倍置,所得到的卷积序列中的最大值就是AB的最大值,但是考虑到精度问题,我们在所得到的卷积序列中只判断极值产生的位置而不是直接获得极值,最后我们从极值产生的位置直接计算答案即可。
【代码】
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring> using namespace std;typedef long long LL;const int N=300000;int n,pos[N];namespace FFT{ struct comp{ double r,i; comp(double _r=0,double _i=0):r(_r),i(_i){} comp operator +(const comp&x){return comp(r+x.r,i+x.i);} comp operator -(const comp&x){return comp(r-x.r,i-x.i);} comp operator *(const comp&x){return comp(r*x.r-i*x.i,i*x.r+r*x.i);} comp conj(){return comp(r,-i);} }A[N],B[N]; const double pi=acos(-1.0); void FFT(comp a[],int n,int t){ for(int i=1;i<n;i++)if(pos[i]>i)swap(a[i],a[pos[i]]); for(int d=0;(1<<d)<n;d++){ int m=1<<d,m2=m<<1; double o=pi*2/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2){ comp w(1,0); for(int j=0;j<m;j++){ comp& A=a[i+j+m],&B=a[i+j],t=w*A; A=B-t; B=B+t; w=w*_w; } } }if(t==-1)for(int i=0;i<n;i++)a[i].r/=n; } void mul(long long *a,long long *b,long long *c,int k){ int i,j; for(i=0;i<k;i++)A[i]=comp(a[i],b[i]); j=__builtin_ctz(k)-1; for(int i=0;i<k;i++){pos[i]=pos[i>>1]>>1|((i&1)<<j);} FFT(A,k,1); for(int i=0;i<k;i++){ j=(k-i)&(k-1); B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*comp(0,-0.25); }FFT(B,k,-1); for(int i=0;i<k;i++)c[i]=(long long)(B[i].r+0.5); }}int T;LL A[N],B[N],C[N],S,M;int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); memset(A,0,sizeof(A));S=0; for(int i=0;i<n;i++)scanf("%lld",&A[n-i-1]); for(int i=0;i<n;i++)scanf("%lld",&B[i]),B[i+n]=B[i]; int N=1; while(N<n*2)N<<=1; FFT::mul(A,B,C,N); M=0; int pos=0; for(int i=0;i<n;i++)if(C[n-1+i]>M)M=C[n-1+i],pos=n-1+i; for(int i=0;i<n;i++,pos--)S=S+(A[i]-B[pos])*(A[i]-B[pos]); printf("%lld\n",S); }return 0;}
hihoCoder 1388 Periodic Signal(FFT)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。