纪念人生第一次FFT

前排感谢iamzky,讲解非常详细

 #include<iostream>
#include<cstdio>
#include<cmath>
using namespace std; const int MAXN=;
class BigNum
{
public:
double r,i;
BigNum(double _r=0.0,double _i=0.0){r=_r;i=_i;}
BigNum operator+(const BigNum T){return BigNum(r+T.r,i+T.i);}
BigNum operator-(const BigNum T){return BigNum(r-T.r,i-T.i);};
BigNum operator*(const BigNum T){return BigNum(r*T.r-i*T.i,r*T.i+i*T.r);};
}; void Brc(BigNum *T,int N)
{
int i,j,k;
for(i=,j=N/;i<N-;i++)
{
if(i<j) swap(T[i],T[j]);
k=N/;
while(j>=k)
{
j-=k;
k>>=;
}
if(j<k) j+=k;
}
} void FFT(BigNum *T,int N,int flag)
{
Brc(T,N);
for(int i=;i<=N;i<<=)
{
BigNum wn(cos(*M_PI/i),flag*sin(*M_PI/i));
for(int j=;j<N;j+=i)
{
BigNum w(,);
for(int k=j;k<j+i/;k++)
{
BigNum u=T[k];
BigNum t=w*T[k+i/];
T[k]=u+t;
T[k+i/]=u-t;
w=w*wn;
}
}
}
if(flag==-)
for(int i=;i<N;i++)
T[i].r/=N;
} string s1,s2;
BigNum A[MAXN],B[MAXN],C[MAXN];
int a[MAXN],b[MAXN],sum[MAXN];
int N; int main()
{
cin>>s1>>s2;
int L1=s1.size();
int L2=s2.size();
for(N=;N<max(L1,L2);N<<=);N<<=;
for(int i=;i<L1;i++) a[L1-i-]=s1[i]-'';
for(int i=;i<L2;i++) b[L2-i-]=s2[i]-'';
for(int i=;i<N;i++) A[i]=BigNum(a[i]);
for(int i=;i<N;i++) B[i]=BigNum(b[i]);
FFT(A,N,);FFT(B,N,);
for(int i=;i<N;i++)C[i]=A[i]*B[i];
FFT(C,N,-);
for(int i=;i<N;i++)sum[i]=C[i].r+0.5;
for(int i=;i<N;i++)
{
sum[i+]+=sum[i]/;
sum[i]%=;
}
int l=L1+L2-;
while(sum[l]==&&l>)l--;
for(int i=l;i>=;i--)
cout<<sum[i];
return ;
}

最新文章

  1. 使用UG UISTYLER 窗体编辑器,创建对话框 part 1
  2. js显示yyyy年mm日dd天 星期几 的格式日期
  3. ajax json 动态传值
  4. sql 联合查询并更新
  5. bzoj1875: [SDOI2009]HH去散步
  6. ZJOI2008泡泡堂BNB
  7. Failed to install apk on device timeout
  8. java_一对一自由聊天
  9. Linking Containers Together
  10. win8命令行
  11. 2017/4/25-SAX解析XML文件
  12. Numpy 操作
  13. (转)Java 网络IO编程总结(BIO、NIO、AIO均含完整实例代码)
  14. JAVA中线程同步方法
  15. 链接生成二维码-PHP
  16. Java中 Linux下安装Redis
  17. JSTL标签库的基本教程之核心标签库(二)
  18. Vue-动态修改数组
  19. MVVM软件设计模式(转)
  20. python记录_day16 类的成员

热门文章

  1. Python学习笔记(迭代,列表解析,生成器)
  2. nodejs动态路由
  3. Java 多线程高并发编程 笔记(一)
  4. CC14:集合栈
  5. Python网络编程之基础
  6. [HNOI2010] 弾飞绵羊
  7. NET Core项目部署
  8. 056 Merge Intervals 合并区间
  9. Cube中维度排序-通过在数据仓库增加列来实现排序
  10. Redis的数据类型(lists、Sets)