首页 > 代码库 > FFT模板

FFT模板

 
#include <cstdio>#include <cmath>#include <cstring>using namespace std; const double pi = acos(-1.0);const int maxn = 500005; struct complex{    double r,i;    complex(double r = 0.0,double i = 0.0) :r(r),i(i) {}    inline complex operator + (const complex &b)   const    {        return complex(r + b.r,i + b.i);    }    inline complex operator - (const complex &b)   const    {        return complex(r - b.r,i - b.i);    }    inline complex operator * (const complex &b)   const    {        return complex(r * b.r - i * b.i,r * b.i + i * b.r);    }    friend inline void swap(complex &a,complex &b)  {   complex t = a;a = b;b = t;  }}; complex a[maxn << 1],b[maxn << 1];int ans[maxn << 1];char szA[maxn],szB[maxn]; inline void fft(complex * y,int n,int on){    for(int mid = n >> 1,i = 1,j = mid;i < n - 1;i ++)    {        if(i < j)   swap(y[i],y[j]);    int k = mid;        for(;j >= k;k >>= 1) j -= k; j += k;    }    for(int h = 2;h <= n;h <<= 1)    {        complex wn(cos(2 * pi / h),sin(on * 2 * pi / h));        for(int j = 0;j < n;j += h)        {            complex w(1,0); int midh = h >> 1;            for(int k = j;k < j + midh;k ++,w = w * wn)            {                complex u = y[k],t = w * y[k + midh];                y[k] = u + t;   y[k + midh] = u - t;            }        }    }    if(on == -1)    for(int i = 0;i < n;i ++)   y[i].r /= n;} int main(){    int lenA,lenB,len;    while(~scanf("%s%s",szA,szB))    {        lenA = strlen(szA),lenB = strlen(szB);        for(len = 1;len < (lenA << 1) || len < (lenB << 1);len <<= 1);        for(int i = 0;i < lenA;i ++)    a[i].r = szA[lenA - i - 1] - ‘0‘,a[i].i = 0;        for(int i = lenA;i < len;i ++)  a[i].r = a[i].i = 0;        for(int i = 0;i < lenB;i ++)    b[i].r = szB[lenB - i - 1] - ‘0‘,b[i].i = 0;        for(int i = lenB;i < len;i ++)  b[i].r = b[i].i = 0;         fft(a,len,1);   fft(b,len,1);        for(int i = 0;i < len;i ++) a[i] = a[i] * b[i];        fft(a,len,-1);         for(int i = 0;i < len;i ++)            ans[i] = a[i].r + 0.5;        for(int i = 0;i < len;i ++) if(ans[i] > 9)  ans[i + 1] += ans[i] / 10,ans[i] %= 10;        int p = lenA + lenB - 1;        while(!ans[p] && p) p --;        while(p >= 0)   putchar(ans[p --] + ‘0‘);        putchar(‘\n‘);    }     return 0;}