【FFT】BZOJ2179- FFT快速傅立叶
2024-10-21 16:39:02
【题目大意】
给出n位十进制a和b,求a*b。
【思路】
FFT。感觉弄起来比较麻烦,不如直接背板子。
注意一下MAXN的取值,我一开始非常随意地就写了60000*2+50,其实n是要扩展到最接近的2的次幂的,所以要取到2^17
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<complex>
#include<cmath>
#define pi acos(-1)
using namespace std;
const int MAXN=131072+5;
typedef complex<double> com;
int n,m,L;
com a[MAXN],b[MAXN];
int c[MAXN],Rev[MAXN]; void get_bit(){for (n=,L=;n<m;n<<=) L++;}
void get_Rtable(){for (int i=;i<n;i++) Rev[i]=(Rev[i>>]>>)|((i&)<<(L-));}
void multi(com* a,com* b){for (int i=;i<n;i++) a[i]*=b[i];} void FFT(com* a,int flag)
{
for (int i=;i<n;i++)if(i<Rev[i])swap(a[i],a[Rev[i]]); //利用逆序表,快速求逆序
for (int i=;i<n;i<<=)
{
com wn(cos(*pi/(i*)),flag*sin(*pi/(i*)));
for (int j=;j<n;j+=(i<<))
{
com w(,);
for (int k=;k<i;k++,w*=wn)
{
com x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;
a[j+k+i]=x-y;
}
}
}
if (flag==-) for (int i=;i<n;i++) a[i]/=n;
} void init()
{
char str[MAXN];
scanf("%d",&n);
scanf("%s",str);
for (int i=;i<n;i++) a[i]=str[n--i]-'';
scanf("%s",str);
for (int i=;i<n;i++) b[i]=str[n--i]-'';
} void solve()
{
m=n<<;//相乘后的位数是原来的2倍
get_bit();
get_Rtable();//求逆序表:末位为0,直接为其前一半逆序表的值右移一位,末位为1,在最高位添加1
FFT(a,),FFT(b,);//分别将a与b的系数表达式转为点值表达式
multi(a,b);//点值表达式相乘
FFT(a,-);//将相乘后的点值表达式转为系数表达式 } void print()
{
for(int i=;i<m;i++) c[i]=(int)(a[i].real()+0.5);
for (;c[m-]==;m--); //把前置的0清空
for (int i=;i<m;i++)
{
if (c[i]>=)
{
c[i+]+=c[i]/;
c[i]%=;
if (i==m-) m++;
}
}
for (int i=m-;i>=;i--) printf("%d",c[i]);
} int main()
{
init();
solve();
print();
return ;
}
最新文章
- mac osx 安装redis扩展
- python整理之(字符串、元组、列表、字典)
- Oracle创建定时器
- Ping 命令的使用方法总结
- Diagramming for WinForms 教程一(读取图元数据)
- Spring使用RowMapper将数据中的每一行封装成用户定义的类
- bzoj 3293 数学整理
- POJ 3237 Tree (树链剖分 路径剖分 线段树的lazy标记)
- Word中表格内容被遮挡
- ural 1106. Two Teams 二分图染色
- Fatal signal 11 (SIGSEGV) at 0xdeadbaad (code=1) 错误 解决方案(android-ndk)
- HDU 5792 World is Exploding
- 常用Vxworks编程API
- 一些User-Agent
- 各种排序算法(C语言)
- Eclipse背景和匹配出现单词的一些设置
- SSM框架原理,作用及使用方法
- python全栈开发day118-Mui
- pm2,部署nodejs,使用方法及自己使用后总结的经验
- Android 打包混淆