注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

FFT初学总结  

2014-06-13 15:42:31|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先对于FFT的大概认识,详见《算导》。
然后贴下大神JYK的代码:
struct node{double x,y;}a[nn*4],b[nn*4],w[2][nn*4];
inline node operator + (node a,node b){return (node){a.x+b.x,a.y+b.y};}
inline node operator - (node a,node b){return (node){a.x-b.x,a.y-b.y};}
inline node operator * (node a,node b){
return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}//node A.x,A.y表示复数A的实部和虚部。注意两个虚部相乘=-1.
void pre()
 {int i,j,x;double e;
  for (i=0;i<n;i++)
    for (j=1,x=i;j<n;j<<=1,x>>=1)(rev[i]<<=1)|=(x&1);//先将二进制反转,如011变为110;

  for (i=0;i<n;i++){
                    e=2.0*pi*i/n;
                    w[0][i]=(node){cos(e),sin(e)};
                    w[1][i]=(node){cos(e),-sin(e)};
                   }//求单位复数根N个点xi。
 }
 
void FFT(node *A,int f)
 {int i,j,t,l,k;node q,p;
  for (i=0;i<n;i++)
    if (rev[i]>i)swap(A[rev[i]],A[i]);//初始交换逆序的二进制。
  for (i=1;i<n;i<<=1)//枚举层数和当前层每块的大小。
   for (j=0,t=n/(i<<1);j<n;j+=(i<<1))//j表示当前层中的起点,t当前层合成的块数。
    for (k=l=0;k<i;k++,l+=t){//j+k表示当前位置,W[F][l]表示当前的单位复数根。
        q=w[f][l]*A[j+k+i];
        p=A[j+k]; A[j+k]=p+q; A[j+k+i]=p-q;//计算
                              }
  if (f)for (i=0;i<n;i++)A[i].x/=n;
 }
 
void mul()
 {int i;
 FFT(a,0);//0表示转成点值表达式
 FFT(b,0);
 for (i=0;i<n;i++)a[i]=a[i]*b[i];//点值可以在O(N)时间内直接相乘。
 FFT(a,1);//1表示转成系数表达式。
 }

一般对于某个问题,将其转换成卷积的形式。ans[j]=Σa[i]*b[j-i](0<=i<=j);

1.bzoj3527: [Zjoi2014]力

将pj提出,就变成了两个裸的卷积,另一个只要初始化逆序即可。用FFT。

2.WiKi3123:大整数相乘

这题真心是裸地卷积,F[i+j]=F[I]*F[J];然后推导出卷积式。

3.bzoj2194:

和力的那题一模一样,就是第二个卷积式。

4.bzoj3509:

分块+FFT,题解详见http://blog.csdn.net/acm_cxlove/article/details/9473839;
但是FFT常数太大,而BZOJ卡得太紧,以上模板会T。只能用NTT 28ms过;
  评论这张
 
阅读(63796)| 评论(8)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018