首页 > 代码库 > bzoj3527: [Zjoi2014]力
bzoj3527: [Zjoi2014]力
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 const int maxn=400005; 8 const double PI=acos(-1); 9 struct node{10 double real,imag;11 void clear(){real=imag=0;}12 node operator +(const node &x){return (node){real+x.real,imag+x.imag};}13 node operator -(const node &x){return (node){real-x.real,imag-x.imag};}14 node operator *(const node &x){return (node){real*x.real-imag*x.imag,real*x.imag+imag*x.real};}15 }q[maxn],p[maxn],A[maxn],t1,t2,w,wn;16 int m,n,len,rev[maxn];17 int Rev(int x){18 int temp=0;19 for (int i=1;i<=len;i++){temp<<=1,temp+=(x&1),x>>=1;}20 return temp;21 }22 void FFT(node *a,int op){23 for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);24 for (int s=2;s<=n;s<<=1){25 wn=(node){cos(2.0*op*PI/s),sin(2.0*op*PI/s)};26 for (int i=0;i<n;i+=s){27 w=(node){1,0};28 for (int j=i;j<i+s/2;j++,w=w*wn){29 t1=a[j],t2=w*a[j+s/2];30 a[j]=t1+t2,a[j+s/2]=t1-t2;31 }32 }33 }34 }35 int main(){36 scanf("%d",&m); n=1,len=0;37 while (n<(m<<1)) n<<=1,len++;38 for (int i=0;i<n;i++) rev[i]=Rev(i);39 for (int i=0;i<n;i++) p[i].clear(),q[i].clear();40 for (int i=1;i<=m;i++) scanf("%lf",&q[i].real);41 for (int i=0;i<m;i++) p[i].real=-1.0/(i-m)/(i-m);42 p[m].real=0; for (int i=m+1;i<n;i++) p[i].real=1.0/(i-m)/(i-m);43 FFT(q,1),FFT(p,1);44 for (int i=0;i<n;i++) A[i]=q[i]*p[i];45 FFT(A,-1);46 for (int i=0;i<n;i++) A[i].real=1.0*A[i].real/n;47 for (int i=1;i<=m;i++) printf("%.3lf\n",A[m+i].real);48 return 0;49 }50
题目大意;题意上网找吧。
做法:我们令A[i+n]=E[n],然后修改一个数组的定义,就是裸的卷积了,直接FFT,详见16年国家集训队论文。
bzoj3527: [Zjoi2014]力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。