首页 > 学院 > 开发设计 > 正文

【ZJOI2014】力

2019-11-08 18:46:28
字体:
来源:转载
供稿:网友

Description

这里写图片描述

Solution

这是第一次打FFT,对于一个新算法,有模板题可以打还是吼开心的。 很明显的要把上面的><和qi给化掉。然后因为有要往后取得,所以把原序列翻转一下后面的放到前面来。 那么Fj=∑j−1i=0qi∗pj−i−∑j−1i=0q′ipj−i q′表示原数组翻转之后的数组,p表示1i∗i 可以发现上面的式子是一个卷积的形式。 由于第一次学FFT,并不知道FFT与卷积有什么关系。 但是研究了一下多项式乘以多项式就可以发现,多项式乘出来之后每隔位置的值就是它对应的卷积形式:∑i=n−1i=0F[i]∗G[n−i] 富榄说只有i到n-1的时候才能用这种形式 然后用FFT直接套上就好了。

Code

#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<math.h>#define fo(i,a,b) for(i=a;i<=b;i++)typedef double db;const int maxn=3e5+7;const db pi=acos(-1);using namespace std;int i,j,k,l,t,n,m,ans,wei,len;db d[maxn],e[maxn];struct Z{ db a,b; Z friend Operator +(Z x,Z y){Z z={x.a+y.a,x.b+y.b};return z;} Z friend operator -(Z x,Z y){Z z={x.a-y.a,x.b-y.b};return z;} Z friend operator *(Z x,Z y){Z z={x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a};return z;}}a[maxn],b[maxn],c[maxn],yi[maxn],er[maxn],bb[maxn];void DFT(Z *a,int bz){ int i,j,k; fo(i,0,len-1){ int o=0,t=i; fo(j,1,wei){o=(o<<1)+(t&1);t/=2;} bb[o]=a[i]; } for(i=2;i<=len;i*=2){ int half=i/2; fo(j,0,half-1){ Z w={cos(pi*j*bz/half),sin(pi*j*bz/half)}; for(k=j;k<len;k+=i){ Z u=bb[k],v=bb[k+half]*w; bb[k]=u+v; bb[k+half]=u-v; } } } if(bz==-1)fo(i,0,len-1)bb[i].a/=len; fo(i,0,len-1)a[i]=bb[i];}void FFT(Z *a,Z *b,db *c){ int i; fo(i,0,len-1)yi[i]=a[i],er[i]=b[i]; DFT(yi,1),DFT(er,1); fo(i,0,len-1)yi[i]=yi[i]*er[i]; DFT(yi,-1); fo(i,1,n)c[i]=yi[i].a;}int main(){// freopen("fan.in","r",stdin);// freopen("fan.out","w",stdout); scanf("%d",&n); len=1;while(len<n*2)len*=2;wei=log(len)/log(2); fo(i,1,n)b[i].a=db(1.0/i/i); fo(i,1,n)scanf("%lf",&a[i].a),c[n-i+1]=a[i]; FFT(a,b,d),FFT(c,b,e); fo(i,1,n)PRintf("%.3lf/n",d[i]-e[n-i+1]);}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表