bzoj 3527: [Zjoi2014]力快速傅里叶变换

2019-11-06 07:46:19

字体：大中小

来源：转载

供稿：网友

题意

给出n个数qi，给出Fj的定义如下：这里写图片描述令Ei=Fi/qi，求Ei. n<=100000

分析

打个表出来就可以发现规律：设a[i]=qi,b[i]=1i2，那么Ej=∑a[i]∗b[j−i]−∑a[i]∗b[i−j] $设a[i]=q_i,b[i]=/frac{1}{i^2}，那么Ej=/sum a[i]*b[j-i]-/sum a[i]*b[i-j]$

可以发现前一个式子原来就是卷积的形式，第二个式子将数组a反过来也变成了卷积形式，直接求即可。

代码

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<complex>#include<cmath>#define MAXN 300005#define pi acos(-1)using namespace std;typedef complex<double> com;int n,N,lg,rev[MAXN];com a[MAXN],b[MAXN],c[MAXN],d[MAXN];void bitrev(){ for (int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));}void fft(com *a,int f){ for (int i=0;i<N;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int i=1;i<N;i<<=1) { com wn(cos(pi/i),f*sin(pi/i)); for (int j=0;j<N;j+=(i<<1)) { com w(1,0); for (int k=0;k<i;k++) { com u=a[j+k],v=w*a[j+k+i]; a[j+k]=u+v;a[j+k+i]=u-v; w*=wn; } } } if (f==-1) for (int i=0;i<N;i++) a[i]/=N;}int main(){ scanf("%d",&n); for (N=1;N<=n*2;N<<=1,lg++); for (int i=1;i<=n;i++) { double x; scanf("%lf",&x); a[i]=c[n-i+1]=x;b[i]=d[i]=(double)1.0*1/i/i; } bitrev(); fft(a,1);fft(b,1); for (int i=0;i<N;i++) a[i]=a[i]*b[i]; fft(a,-1); fft(c,1);fft(d,1); for (int i=0;i<N;i++) c[i]=c[i]*d[i]; fft(c,-1); for (int i=1;i<=n;i++) PRintf("%.3lf/n",a[i].real()-c[n-i+1].real()); return 0;}

上一篇：lanqiao-矩阵乘法

下一篇：并查集_HDU1325_Is It A Tree?