[BZOJ2179]-大数乘法-FFT模板

说在前面

这题输入输出真的有毒…
细节调了me一晚上= =#…

题目

BZOJ2179传送门

题面

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

输入输出格式

输入格式：
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y

输出格式：
输出一行，即x*y的结果

解法

真 ? FFT模板
把一个数字 A 写成这样 A=∑i=0位数?1ai?10i?1 ，就是一个多项式了=w= 直接上FFT即可
注意读入数字的时候，数组下标小的存低位，下标大的存高位，这样写更方便进位，并且不用判断后缀0

下面是自带大常数的代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

const double PI = 3.1415926535897932384626 ;
int N,len,expos[131100],ans[131100] ;
char ssa[131100],ssb[131100] ;
struct Complex{
    double x,y ;
    Complex(){} ;
    Complex( double x_,double y_ ):
        x(x_),y(y_) {} ;
} ;
typedef Complex cpx ;
cpx a[131100],b[131100] ;
cpx operator + ( const cpx &A,const cpx &B ){ return cpx( A.x+B.x,A.y+B.y ); }
cpx operator - ( const cpx &A,const cpx &B ){ return cpx( A.x-B.x,A.y-B.y ); }
cpx operator * ( const cpx &A,const cpx &B ){ return cpx( A.x*B.x - A.y*B.y,A.x*B.y + A.y*B.x ); }
cpx operator / ( const cpx &A,const double &p ){ return cpx( A.x/p,A.y/p ) ; }

void FFT( cpx *a,int fix ){
    for( int i = 1 ; i < N ; i ++ )
        if( expos[i] > i ) swap( a[i],a[ expos[i] ] ) ;
    for( int id = 2 ; id <= N ; id <<= 1 ){
        cpx Wid = cpx( cos( 2 * PI * fix / id ),sin( 2 * PI * fix / id ) ) ;
        for( int j = 0 ; j < N ; j += id ){
            cpx W = cpx( 1,0 ) ;
            for( int k = j ; k < j + id/2 ; k ++ ){
                cpx u = a[k],v = a[k+id/2] ;
                a[k] = u + v * W ;
                a[k+id/2] = u - v * W ;
                W = W * Wid ;
            }
        }
    }
    if( fix == -1 )
        for( int i = 0 ; i < N ; i ++ )
            a[i] = a[i] / N ;
}

void solve(){
    FFT( a,1 ) ;
    FFT( b,1 ) ;
    for( int i = 0 ; i < N ; i ++ )
        a[i] = a[i] * b[i] ;
    FFT( a,-1 ) ;

    int anslen = 2 * len - 1 ;
    for( int i = 0 ; i <= 2 * len - 1 ; i ++ ){
        ans[i] += a[i].x + 0.5 ;
        if( ans[i] >= 10 ){
            ans[i+1] += ans[i]/10 ;
            ans[i] %= 10 ;
        } 
    }
    for( int i = anslen ; i >= 0 ; i -- )
        if( ans[i] != 0 ){
            for( int j = i ; j >= 0 ; j -- )
                printf( "%d",ans[j] ) ;
            return ;
        }
}

int main(){
    scanf( "%d",&len ) ;
    scanf( "%s%s",ssa,ssb ) ;
    for( int i = 1 ; ; i <<= 1 )
        if( i >= len * 2 ){ N = i ; break ; }
    for( int i = 0 ; i < len ; i ++ )
        a[len-i-1].x = ssa[i] - '0',b[len-i-1].x = ssb[i] - '0' ;
    for( int i = 1,aim = 0 ; i < N ; i ++ ){
        int tmp = N >> 1 ;
        while( aim&tmp ) aim ^= tmp,tmp >>= 1 ;
        aim ^= tmp ; expos[i] = aim ;
    }
    solve() ;
}

一点理解

FFT优化的不是单项运算，而是一次性把 ω0n 到 ωn?1n 算完
每次都是把一个多项式拆分成两个多项式的和与差
A[ωkn]=A′[ωkn2]+A′′[ωkn2]
A[ωk+n2n]=A′[ωkn2]?A′′[ωkn2]
数组里存的就是这些 A[] 的结果，由 A′ 和 A′′ 算出两个 A ，这样不会增加空间，时间也变成了 log