【bzoj3527】[Zjoi2014]力 FFT

2016-06-01  21:36:44

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3527

我就是一个大傻叉 微笑脸

 #include<bits/stdc++.h>
#define inf 1000000000
#define ll long long
#define N 500005
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const double Pi=acos(-1.0);
struct CD{
double x,y;
CD(double a=,double b=){x=a,y=b;}
friend CD operator + (CD n1,CD n2){return CD(n1.x+n2.x,n1.y+n2.y);}
friend CD operator - (CD n1,CD n2){return CD(n1.x-n2.x,n1.y-n2.y);}
friend CD operator * (CD n1,CD n2){return CD(n1.x*n2.x-n1.y*n2.y,n1.x*n2.y+n1.y*n2.x);}
};
CD a[N],b[N],c[N],d[N];
int n,nn,bit;
double q[N];
void FFT(CD *a,int n,int type){
for(int i=,j=;i<n;i++){
if(j>i)swap(a[i],a[j]);
int k=n;
while(j&(k>>=))j&=~k;
j|=k;
}
for(int i=;i<=bit;i++){
CD w_n(cos(*type*Pi/(<<i)),sin(*type*Pi/(<<i)));
for(int j=;j<(<<bit);j+=(<<i)){
CD w(,);
for(int k=j;k<j+(<<(i-));k++){
CD tmp=a[k],tt=w*a[k+(<<(i-))];
a[k]=tmp+tt;a[k+(<<(i-))]=tmp-tt;
w=w*w_n;
}
}
}
if(type<)for(int i=;i<n;i++)a[i].x=a[i].x/n;
}
int main(){
n=read();nn=n;
for(int i=;i<n;i++)scanf("%lf",&q[i]),a[i]=CD(q[i],);
for(int i=;i<n;i++)b[i].x=1.0/(double)(i*i),b[i].y=;
n=*n-;bit=;
while((<<bit)<n)bit++;
n=<<bit;
b[]=CD();
for(int i=nn;i<n;i++)a[i]=CD(),b[i]=CD(); FFT(a,n,);FFT(b,n,);
for(int i=;i<n;i++)c[i]=a[i]*b[i];
FFT(c,n,-);
for(int i=;i<nn;i++)a[i]=CD(q[nn-i-],);
for(int i=nn;i<n;i++)a[i]=CD();
FFT(a,n,);
for(int i=;i<n;i++)d[i]=a[i]*b[i];
FFT(d,n,-); for(int i=;i<nn;i++)c[i].x-=d[nn-i-].x;
for(int i=;i<nn;i++)printf("%.5lf\n",c[i].x);
return ;
}
上一篇:Spring消息之AMQP.


下一篇:iOS-程序发布-32位和64位系统的兼容