【BZOJ2179】FFT快速傅立叶

Description

给出两个n位10进制整数x和y,你需要计算x*y。

Input

第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。

Output

输出一行,即x*y的结果。

Sample Input

1
3
4

Sample Output

12

数据范围:

n<=60000

题解:板子题,敲板子~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define pi acos(-1.0)
using namespace std;
struct cp
{
double x,y;
cp(double x0,double y0)
{
x=x0,y=y0;
}
cp(){}
cp operator +(const cp a)const
{
return cp(x+a.x,y+a.y);
}
cp operator -(const cp a)const
{
return cp(x-a.x,y-a.y);
}
cp operator *(const cp a)const
{
return cp(x*a.x-y*a.y,x*a.y+y*a.x);
}
}n1[1<<20],n2[1<<20];
int n;
char str[1<<20];
int ans[1<<20];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void init(cp *a,int len)
{
int i,j,t=0;
for(i=0;i<len;i++)
{
if(i>t) swap(a[i],a[t]);
for(j=(len>>1);(t^=j)<j;j>>=1);
}
}
void FFT(cp *a,int len,int f)
{
init(a,len);
int h,i,j,k;
cp t;
for(h=2;h<=len;h<<=1)
{
cp wn(cos(f*2*pi/h),sin(f*2*pi/h));
for(j=0;j<len;j+=h)
{
cp w(1,0);
for(k=j;k<j+h/2;k++) t=w*a[k+h/2],a[k+h/2]=a[k]-t,a[k]=a[k]+t,w=w*wn;
}
}
if(f==-1) for(i=0;i<len;i++) a[i].x=a[i].x/len;
}
void work(cp *a,cp *b,int len)
{
FFT(a,len,1),FFT(b,len,1);
for(int i=0;i<len;i++) a[i]=a[i]*b[i];
FFT(a,len,-1);
for(int i=0;i<len;i++) ans[i]=int(a[i].x+0.1);
}
int main()
{
n=rd();
int i,j,t=0,len=1;
while(len<n*2) len<<=1;
scanf("%s",str);
for(i=0;i<n;i++) n1[n-i-1]=cp(str[i]-'0',0);
scanf("%s",str);
for(i=0;i<n;i++) n2[n-i-1]=cp(str[i]-'0',0);
for(i=n;i<len;i++) n1[i]=n2[i]=cp(0,0);
work(n1,n2,len);
len=2*n-1;
for(i=0;i<=len;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
while(ans[len]<=0&&len) len--;
for(i=len;i>=0;i--) printf("%d",ans[i]);
return 0;
}

最新文章

  1. Java将文件转为字节数组
  2. vs2013卸载后重新安装不能用了,如何解决
  3. 【转】APNs消息推送完整讲解
  4. jdbc根据实例名 连接 sql server
  5. JQuery时间轴timeline插件的学习-Lateral On-Scroll Sliding with jQuery+technotarek / timeliner
  6. [Everyday Mathematics]20150225
  7. lucene4入门(2)搜索
  8. 求一个数组中第K小的数
  9. 关于Connection must be valid and open.
  10. Oracle OS认证和口令文件认证方法
  11. 转载 C#文件上传
  12. windows下更改mysql数据储存物理目录
  13. eclipse 包 取消代码第一行package包名 自动补全时取消自动引入包名 修改名字 取消引用 自动导入publilc static void main(String[] args) {}
  14. elasticSearch学习安装
  15. 通过 curl 传递数据
  16. Linux .vimrc 设置项
  17. Nginx自动安装脚本
  18. 在同一台电脑安装python 2 和3,并且怎样安装各自的pip和模块
  19. js高级-模块化演变
  20. Android 获取自带浏览器上网记录

热门文章

  1. Oracle 性能调优案例(代码级别)
  2. java类的初始化和构造函数
  3. C语言printf格式化输出修饰符详解
  4. SQL数据库相关
  5. C#使用技巧之调用JS脚本(转)
  6. 实现Windows Server 2003多用户远程登录(转载)
  7. 定时检测Memcached进程是否存在,若不存在自动启动它
  8. [elk]logstash的grok匹配逻辑grok+date+mutate
  9. 将json数组字符串转换为json数组对象(值是json对象的数组)
  10. 辛星和你彻底搞清CSS中的相对定位和绝对定位