【ZJOI2014】力

2019-11-08 18:46:28

字体：大中小

来源：转载

供稿：网友

Description

这里写图片描述

Solution

这是第一次打FFT，对于一个新算法，有模板题可以打还是吼开心的。很明显的要把上面的＞＜和qi给化掉。然后因为有要往后取得，所以把原序列翻转一下后面的放到前面来。那么Fj=∑j−1i=0qi∗pj−i−∑j−1i=0q′ipj−i $F_j=/sum_{i=0}^{j-1}q_i*p_{j-i}-/sum_{i=0}^{j-1}q'_ip_{j-i}$ q′表示原数组翻转之后的数组，p表示1i∗i $q'表示原数组翻转之后的数组，p表示{1/over i*i}$ 可以发现上面的式子是一个卷积的形式。由于第一次学FFT，并不知道FFT与卷积有什么关系。但是研究了一下多项式乘以多项式就可以发现，多项式乘出来之后每隔位置的值就是它对应的卷积形式：∑i=n−1i=0F[i]∗G[n−i] $/sum_{i=0}^{i=n-1}F[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]);}

上一篇：正则表达式（1）——基础知识

下一篇：@requestParam 注解

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注