借着别人的码装完逼就跑系列
一个写的堪称完美的贴纸： http://www.gatevin.moe/acm/fft算法学习笔记/
FFT模板 计算A * B
#include <algorithm> #include <bitset> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <vector> using namespace std; const double eps ( 1e-8 ); typedef long long lint; const double PI = acos ( -1.0 ); struct Complex { double real, image; Complex ( double _real, double _image ) { real = _real; image = _image; } Complex () {} }; Complex operator+ ( const Complex &c1, const Complex &c2 ) { return Complex ( c1.real + c2.real, c1.image + c2.image ); } Complex operator- ( const Complex &c1, const Complex &c2 ) { return Complex ( c1.real - c2.real, c1.image - c2.image ); } Complex operator* ( const Complex &c1, const Complex &c2 ) { return Complex ( c1.real * c2.real - c1.image * c2.image, c1.real * c2.image + c1.image * c2.real ); } // 循环FFT的顺序刚好是每个id位逆序排序后的顺序 int rev ( int id, int len ) { int ret = 0; for ( int i = 0; ( 1 << i ) < len; i++ ) { ret <<= 1; if ( id & ( 1 << i ) ) ret |= 1; } return ret; } //当DFT= 1时是DFT, DFT = -1则是逆DFT Complex A[ 140000 ]; void IterativeFFT ( Complex *a, int len, int DFT ) //对长度为len(2的幂)的数组进行DFT变换 { // Complex *A = new Complex[ len ]; //用A数组存储数组a分组之后新的顺序 for ( int i = 0; i < len; i++ ) A[ rev ( i, len ) ] = a[ i ]; for ( int s = 1; ( 1 << s ) <= len; s++ ) { int m = ( 1 << s ); Complex wm = Complex ( cos ( DFT * 2 * PI / m ), sin ( DFT * 2 * PI / m ) ); for ( int k = 0; k < len; k += m ) //这一层结点的包含数组元素个数都是(1 << s) { Complex w = Complex ( 1, 0 ); for ( int j = 0; j < ( m >> 1 ); j++ ) //折半引理, 根据两个子节点计算父亲节点 { Complex t = w * A[ k + j + ( m >> 1 ) ]; Complex u = A[ k + j ]; A[ k + j ] = u + t; A[ k + j + ( m >> 1 ) ] = u - t; w = w * wm; } } } if ( DFT == -1 ) for ( int i = 0; i < len; i++ ) A[ i ].real /= len, A[ i ].image /= len; for ( int i = 0; i < len; i++ ) a[ i ] = A[ i ]; return; } char numA[ 50010 ], numB[ 50010 ]; Complex a[ 140000 ], b[ 140000 ]; int ans[ 140000 ]; int main () { while ( ~scanf ( "%s", numA ) ) { int lenA = strlen ( numA ); int sa = 0; //lenA有多少位好吗 while ( ( 1 << sa ) < lenA ) sa++; scanf ( "%s", numB ); int lenB = strlen ( numB ); int sb = 0; //lenB有多少位 while ( ( 1 << sb ) < lenB ) sb++; //计算模板里的len，相当于算出A和B中最多有多少位的二次幂（ FFT 深度 = lg（len）） int len = ( 1 << ( max ( sa, sb ) + 1 ) ); //字符串转化为整数 for ( int i = 0; i < len; i++ ) { if ( i < lenA ) a[ i ] = Complex ( numA[ lenA - i - 1 ] - '0', 0 ); else a[ i ] = Complex ( 0, 0 ); if ( i < lenB ) b[ i ] = Complex ( numB[ lenB - i - 1 ] - '0', 0 ); else b[ i ] = Complex ( 0, 0 ); } //正变换求值 IterativeFFT ( a, len, 1 ); IterativeFFT ( b, len, 1 ); //计算A*B for ( int i = 0; i < len; i++ ) a[ i ] = a[ i ] * b[ i ]; //反变换得到C的系数 IterativeFFT ( a, len, -1 ); // 复数变整数？？？？懵逼.jpg for ( int i = 0; i < len; i++ ) ans[ i ] = (int)( a[ i ].real + 0.5 ); // 进位 for ( int i = 0; i < len - 1; i++ ) { ans[ i + 1 ] += ans[ i ] / 10; ans[ i ] %= 10; } bool flag = 0; //输出 for ( int i = len - 1; i >= 0; i-- ) { if ( ans[ i ] ) printf ( "%d", ans[ i ] ), flag = 1; else if ( flag || i == 0 ) printf ( "0" ); } putchar ( '\n' ); } return 0; }