【题目大意】

给出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 ;
}

最新文章

  1. mac osx 安装redis扩展
  2. python整理之(字符串、元组、列表、字典)
  3. Oracle创建定时器
  4. Ping 命令的使用方法总结
  5. Diagramming for WinForms 教程一(读取图元数据)
  6. Spring使用RowMapper将数据中的每一行封装成用户定义的类
  7. bzoj 3293 数学整理
  8. POJ 3237 Tree (树链剖分 路径剖分 线段树的lazy标记)
  9. Word中表格内容被遮挡
  10. ural 1106. Two Teams 二分图染色
  11. Fatal signal 11 (SIGSEGV) at 0xdeadbaad (code=1) 错误 解决方案(android-ndk)
  12. HDU 5792 World is Exploding
  13. 常用Vxworks编程API
  14. 一些User-Agent
  15. 各种排序算法(C语言)
  16. Eclipse背景和匹配出现单词的一些设置
  17. SSM框架原理,作用及使用方法
  18. python全栈开发day118-Mui
  19. pm2,部署nodejs,使用方法及自己使用后总结的经验
  20. Android 打包混淆

热门文章

  1. vue数组操作不触发前端重新渲染
  2. Python作业模拟登陆(第一周)
  3. hdu 1162 Eddy&#39;s picture(最小生成树算法)
  4. Android中TextView设置字体
  5. ubuntu安装wifi
  6. 從 kernel source code 查出 版本號碼
  7. python基础===Sublime Text 3 快捷键
  8. MinnowBoard
  9. 访问WEB-INF目录中的文件
  10. 动画基础--基于Core Animation(1)