【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)