bzoj3527: [Zjoi2014]力

时间：2022-09-22 00:06:32
 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int maxn=;

 const double PI=acos(-);

 struct node{

     double real,imag;

     void clear(){real=imag=;}

     node operator +(const node &x){return (node){real+x.real,imag+x.imag};}

     node operator -(const node &x){return (node){real-x.real,imag-x.imag};}

     node operator *(const node &x){return (node){real*x.real-imag*x.imag,real*x.imag+imag*x.real};}

 }q[maxn],p[maxn],A[maxn],t1,t2,w,wn;

 int m,n,len,rev[maxn];

 int Rev(int x){

     int temp=;

     for (int i=;i<=len;i++){temp<<=,temp+=(x&),x>>=;}

     return temp;

 }

 void FFT(node *a,int op){

     for (int i=;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);

     for (int s=;s<=n;s<<=){

         wn=(node){cos(2.0*op*PI/s),sin(2.0*op*PI/s)};

         for (int i=;i<n;i+=s){

             w=(node){,};

             for (int j=i;j<i+s/;j++,w=w*wn){

                 t1=a[j],t2=w*a[j+s/];

                 a[j]=t1+t2,a[j+s/]=t1-t2;

             }

         }

     }

 }

 int main(){

     scanf("%d",&m); n=,len=;

     while (n<(m<<)) n<<=,len++;

     for (int i=;i<n;i++) rev[i]=Rev(i);

     for (int i=;i<n;i++) p[i].clear(),q[i].clear();

     for (int i=;i<=m;i++) scanf("%lf",&q[i].real);

     for (int i=;i<m;i++) p[i].real=-1.0/(i-m)/(i-m);

     p[m].real=; for (int i=m+;i<n;i++) p[i].real=1.0/(i-m)/(i-m);

     FFT(q,),FFT(p,);

     for (int i=;i<n;i++) A[i]=q[i]*p[i];

     FFT(A,-);

     for (int i=;i<n;i++) A[i].real=1.0*A[i].real/n;

     for (int i=;i<=m;i++) printf("%.3lf\n",A[m+i].real);

     return ;

 }

题目大意；题意上网找吧。

做法：我们令A[i+n]=E[n],然后修改一个数组的定义，就是裸的卷积了，直接FFT，详见16年国家集训队论文。

相关文章