洛谷P1919 【模板】A*B Problem升级版（FFT快速傅里叶）-白红宇

洛谷P1919 【模板】A*B Problem升级版（FFT快速傅里叶）

阅读量：6439 次

发布时间：2019-06-23

本文共 1420 字，大约阅读时间需要 4 分钟。

题目描述

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

输入输出格式

输入格式：

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

输出格式：

输出一行，即x*y的结果。（注意判断前导0）

输入输出样例

输入样例#1：

输出样例#1：

说明

数据范围：

n<=60000

来源：bzoj2179

本题数据为洛谷自造数据，使用耗时5分钟完成数据制作。

emmmm感觉学了FFT没什么乱用啊，，

也就来水一水这种板子吧。

思路很简单，将每一位看成多项式的系数。

来一遍FFT

最后去掉前导0

输出

不过话说我的FFT怎么这么慢

#include
     
      #include
      
       #include
       
        using namespace std;const int MAXN=1e5+10;const double Pi=acos(-1.0);int r[MAXN],l=0,limit=1,c[MAXN];char sa[MAXN],sb[MAXN];struct complex{    double x,y;    complex(double xx=0,double yy=0){x=xx,y=yy;}}a[MAXN],b[MAXN];complex operator + (complex a,complex b){
   return complex(a.x+b.x,a.y+b.y);}complex operator - (complex a,complex b){
   return complex(a.x-b.x,a.y-b.y);}complex operator * (complex a,complex b){
   return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}void FFT(complex *a,int type){    for(int i=0;i
        
         >1]>>1) | ((i&1)<<(l-1) );    FFT(a,1);    FFT(b,1);    for(int i=0;i<=limit;i++) a[i]=a[i]*b[i];    FFT(a,-1);    for(int i=0;i<=limit;i++) c[i]=(int)(a[i].x/limit+0.5);    //for(int i=1;i<=limit;i++) printf("%d ",c[i]);printf("\n");    for(int i=0;i<=limit;i++)    {        if(c[i]>10)        {            c[i+1]+=c[i]/10,c[i]%=10;            if(i+1>limit) limit++;        }    }    for(int i=limit;i>=0;i--)        if(c[i]==0) limit--;        else break;    for(int i=limit;i>=0;i--)        printf("%d",c[i]);    return 0;}