传送门

话说FFT该不会真的只能用来做这种板子吧……

我们把两个数字的每一位都看作多项式的系数

然后这就是一个多项式乘法

上FFT就好了

然后去掉前导零

(然而连FFT的板子都背不来orz,而且空间又开小了……)

 //minamoto
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);
}
const int N=2e5+;const double Pi=acos(-1.0);
int r[N],l=,limit=,c[N],n;char sa[N],sb[N];
struct complex{
double x,y;
complex(double xx=,double yy=){x=xx,y=yy;}
inline complex operator +(complex b){return complex(x+b.x,y+b.y);}
inline complex operator -(complex b){return complex(x-b.x,y-b.y);}
inline complex operator *(complex b){return complex(x*b.x-y*b.y,x*b.y+y*b.x);}
}a[N],b[N];
void FFT(complex *a,int type){
for(int i=;i<limit;++i)
if(i<r[i]) swap(a[i],a[r[i]]);
for(int mid=;mid<limit;mid<<=){
complex Wn(cos(Pi/mid),type*sin(Pi/mid));
for(int R=mid<<,j=;j<limit;j+=R){
complex w(,);
for(int k=;k<mid;++k,w=w*Wn){
complex x=a[j+k],y=w*a[j+k+mid];
a[j+k]=x+y,a[j+k+mid]=x-y;
}
}
}
}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d",&n),--n;
scanf("%s%s",sa,sb);
for(int i=;i<=n;++i) a[i].x=sa[n-i]-'',b[i].x=sb[n-i]-'';
while(limit<=n*) limit<<=,++l;
for(int i=;i<=limit;++i) r[i]=(r[i>>]>>)|((i&)<<(l-));
FFT(a,),FFT(b,);
for(int i=;i<=limit;++i) a[i]=a[i]*b[i];
FFT(a,-);
for(int i=;i<=limit;++i) c[i]=(int)(a[i].x/limit+0.5);
for(int i=;i<=limit;++i)
if(c[i]>){
c[i+]+=c[i]/,c[i]%=;
if(i+>limit) ++limit;
}
for(int i=limit;i>=;--i)
if(c[i]==) --limit;
else break;
for(int i=limit;i>=;--i) print(c[i]);
Ot();
return ;
}

最新文章

  1. JavaScript自运行函数(function(){})()的理解
  2. zozoui
  3. JavaScript数组类型
  4. [2]R语言在数据处理上的禀赋之——可视化技术
  5. Linux内核实现中断和中断处理(二)
  6. 通过实验窥探javascript的解析执行顺序
  7. Viewpager模仿微信主布局的三种方式 ViewPager,Fragment,ViewPager+FragmentPagerAdapter
  8. bug
  9. java.lang.Boolean为null时
  10. Proud Merchants(POJ 3466 01背包+排序)
  11. Javascript中undefined,NaN等特殊比较
  12. mini2440驱动奇谭——ADC驱动与測试(动态挂载驱动)
  13. css div 细边框
  14. 使用强类型实体Id来避免原始类型困扰(一)
  15. Android Studio多渠道打包(二)
  16. python学习路程1
  17. DHT
  18. helloworld讲解cocos2d-x的编程思路与要点
  19. cplusplus 库 在线管理; 类似于 python的 pip install 、nodejs 的npm模块
  20. JAVA-数据库之Statement对象

热门文章

  1. 使用jquery datatables插件遇到fnReloadAjax的问题
  2. bjfu1332 简单动规
  3. c#冒泡法排序
  4. 2018.11.23-day27 面向对象(大总结)
  5. Boosting AdaBoosting Algorithm
  6. SpringBoot-(6)-日志SLF4j
  7. “cannot be resolved to a type” 错误解决方法
  8. html5--3.9 input元素(8)
  9. Java版本更新历史(ing)
  10. Messes in Reading Source Coding of SSD