首页 > 代码库 > BZOJ 2179 [快速傅里叶变换 高精度乘法]

BZOJ 2179 [快速傅里叶变换 高精度乘法]

2179: FFT快速傅立叶

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 3108  Solved: 1599
[Submit][Status][Discuss]

Description

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

Input

第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。
 
数据范围:
n<=60000

扔个模板
注意读入字符转换成系数 系数转换成整数
#include <iostream>#include <cstdio>#include <string>#include <algorithm>#include <cmath>using namespace std;const int N=3e5+5;const double PI=acos(-1);inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}struct Vector{    double x,y;    Vector(double a=0,double b=0):x(a),y(b){}};typedef Vector CD;Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}Vector operator *(Vector a,Vector b){return Vector(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}Vector operator /(Vector a,int b){return Vector(a.x/b,a.y/b);}Vector conj(Vector a){return Vector(a.x,-a.y);}struct FastFourierTransform{    CD omega[N],omegaInv[N];    void ini(int n){        for(int k=0;k<n;k++)             omega[k]=CD(cos(2*PI/n*k),sin(2*PI/n*k)),            omegaInv[k]=conj(omega[k]);    }    void transform(CD *a,int n,CD *omega){        int k=0;        while((1<<k)<n) k++;        for(int i=0;i<n;i++){            int t=0;            for(int j=0;j<k;j++) if(i&(1<<j)) t|=(1<<(k-j-1));            if(i>t) swap(a[t],a[i]);        }                for(int l=2;l<=n;l<<=1){            int m=l>>1;            for(CD *p=a;p!=a+n;p+=l)                for(int k=0;k<m;k++){                    CD t=omega[n/l*k]*p[k+m];                    p[k+m]=p[k]-t;                    p[k]=p[k]+t;                }        }    }    void DFT(CD *a,int n){transform(a,n,omega);}    void IDFT(CD *a,int n){        transform(a,n,omegaInv);        for(int i=0;i<n;i++) a[i]=a[i]/n;    }    void FFT(CD *a,CD *b,int m){        int n=1;        while(n<m) n<<=1;        ini(n);        DFT(a,n);DFT(b,n);        for(int i=0;i<n;i++) a[i]=a[i]*b[i];        IDFT(a,n);    }}fft;CD A[N],B[N];int n,m,c[N];char s1[N],s2[N];int main(){    freopen("in","r",stdin);    n=read();m=n+n-1;    scanf("%s%s",s1,s2);    for(int i=0;i<n;i++) A[i].x=s1[n-i-1]-0,B[i].x=s2[n-i-1]-0;    fft.FFT(A,B,m);    for(int i=0;i<m;i++) c[i]=int(A[i].x+0.5);//printf("c %d\n",c[i]);    for(int i=0;i<m;i++) c[i+1]+=c[i]/10,c[i]%=10;    while(c[m]) m++;    for(int i=m-1;i>=0;i--) printf("%d",c[i]);    return 0;}

 

BZOJ 2179 [快速傅里叶变换 高精度乘法]