本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

题目链接:HDU1402

正解:FFT

解题报告:

  FFT模板题,注意一下进位处理。

  重要的话说三遍:去掉多余的0!!!WA了几遍…

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
typedef complex<double> C;
const int MAXN = 300011;
const double pi = acos(-1);
char ch[MAXN],s[MAXN];
int n,m,ans[MAXN];
C a[MAXN],b[MAXN]; inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline void fft(C *a,int n,int f){
if(n==1) return ;
C a0[n>>1],a1[n>>1],wn(cos(2*pi/n),sin(2*pi*f/n)),w(1,0),t;
for(int i=0;i<n>>1;i++) a0[i]=a[i<<1],a1[i]=a[i<<1|1];
fft(a0,n>>1,f); fft(a1,n>>1,f);
for(int i=0;i<n>>1;i++,w*=wn) {
t=a1[i]*w;
a[i]=a0[i]+t;
a[i+(n>>1)]=a0[i]-t;
}
} inline void work(){
while(scanf("%s",ch)!=EOF) {
scanf("%s",s); memset(ans,0,sizeof(ans));
memset(a,0,sizeof(a)); memset(b,0,sizeof(b));//记得清空!
n=strlen(ch); m=strlen(s); n--; m--;
for(int i=n;i>=0;i--) a[n-i]=(int)ch[i]-'0';
for(int i=m;i>=0;i--) b[m-i]=(int)s[i]-'0';
m+=n; for(n=1;n<=m;n<<=1);
fft(a,n,1); fft(b,n,1);
for(int i=0;i<=n;i++) a[i]*=b[i];
fft(a,n,-1);
for(int i=0;i<=m;i++) ans[i]=(int)(a[i].real()/n+0.5);
for(int i=0;i<=m;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
while(ans[m+1]>0) m++,ans[m+1]+=ans[m]/10,ans[m]%=10;
while(ans[m]==0) m--;//注意去掉多余的0!!!
if(m>=0) { for(int i=m;i>=0;i--) printf("%d",ans[i]); puts(""); }
else puts("0");
}
} int main()
{
work();
return 0;
}

  

最新文章

  1. Google公布了禁用Chrome插件后的新解决方案
  2. MyEclipse对Struts2配置文件较检异常 Invalid result location value/parameter
  3. 打包解决方案后,安装时提示只能在IIS5.1以上运行解决方法
  4. Android是如何绘制View的
  5. linux 禁止指定账号ssh登陆
  6. CSS盒子模型小剖析
  7. Jasper_crosstab_group _Error incrementing crosstab dataset
  8. R与数据分析旧笔记(六)多元线性分析 上
  9. C#中linq报“Character literal must contain exactly one character”的错误提示
  10. 由世纪互联运营的 Windows Azure 现已在中国正式发布
  11. JSP知识点大纲图
  12. eval基础,基础用法及解析json
  13. php写一个简洁的登录页面
  14. leetCode之旅(14)-Number of 1 Bits
  15. js如何读写txt文件?(曲线救国篇)
  16. WordPress plugin Contact Form [CSRF → LFI] vulnerable 2019-03-17
  17. GDB 命令回顾
  18. android不知不觉偷拍他人功能实现(手机关闭依然拍照)【申明:来源于网络】
  19. javascript篇-console.log()打印object却显示为字符串[object object]
  20. 如何利用Photoshop进行快速切图

热门文章

  1. GIT界的神探--bisect
  2. 学习js的正确姿势
  3. Delphi中MD5实现方法(转)
  4. JS产品分类列表练习
  5. django.core.exceptions.ImproperlyConfigured: Requested setting DEFAULT_INDEX_TABLESPACE的解决办法(转)
  6. 详解JMeter函数和变量(转载)
  7. 可采用两种方法得到一个EJB对象
  8. 对ASIHTTPRequest的封装
  9. HTML5之WEB Storage
  10. 用仿ActionScript的语法来编写html5——第三篇,鼠标事件与游戏人物移动