FFT快速傅里叶变化
2024-09-08 02:19:00
纪念人生第一次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 ;
}
最新文章
- 使用UG UISTYLER 窗体编辑器,创建对话框 part 1
- js显示yyyy年mm日dd天 星期几 的格式日期
- ajax json 动态传值
- sql 联合查询并更新
- bzoj1875: [SDOI2009]HH去散步
- ZJOI2008泡泡堂BNB
- Failed to install apk on device timeout
- java_一对一自由聊天
- Linking Containers Together
- win8命令行
- 2017/4/25-SAX解析XML文件
- Numpy 操作
- (转)Java 网络IO编程总结(BIO、NIO、AIO均含完整实例代码)
- JAVA中线程同步方法
- 链接生成二维码-PHP
- Java中 Linux下安装Redis
- JSTL标签库的基本教程之核心标签库(二)
- Vue-动态修改数组
- MVVM软件设计模式(转)
- python记录_day16 类的成员