FFT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef long double ld;
const int N = 9000000;
const ld pi = acos(-1);
struct CP {
    ld x, y;
    CP operator+(const CP& a) const {return {x + a.x, y + a.y};}
    CP operator-(const CP& a) const {return {x - a.x, y - a.y};}
    CP operator*(const CP& a) const {return {x * a.x - y * a.y, x * a.y + y * a.x};}
}a[N], b[N];
int rev[N],limit, len, n, m;
void fft(CP a[], int inv) {
    for (int i = 0;i < limit; i ++) 
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
            //
        }
    for (int mid=  1; mid < limit;mid <<= 1) {
        auto w1 = CP({(ld)cos(pi/mid), (ld)inv * (ld)sin(pi/(ld)mid)});
        //cout << mid << ":";
        for (int i = 0; i < limit; i += mid * 2) {
            auto wk = CP({1, 0});
            for (int j = 0; j < mid; j ++, wk = wk * w1) {
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y;
                a[i + j + mid] = x-y;
                
            }
        }
    }
}
char s1[N], s2[N];
ll sum[N];
void clear() {
    for (int i = 0; i < limit; i++) {
        a[i] = CP({0, 0});
        b[i] = CP({0, 0});
        sum[i] = 0;
    }
    len = 0;
    limit = 0;
}
void solve() {
    while (cin >> (s1) >> s2) {
        n = strlen(s1);
        m = strlen(s2);
        reverse(s1, s1 + n);
        reverse(s2, s2 + m);
        n--,m--;
        len = 0;
        for (int i = n; i >= 0; i --)a[i].x = s1[i] - ‘0‘;//, cout << a[i].x;cout << endl;
        for (int i = m; i >= 0; i --)b[i].x = s2[i] - ‘0‘;//, cout << b[i].x;cout << endl;
        while ((1 << len) < n + m + 1)len++;
        limit = 1<<len;
        for (int i = 0; i < limit; i ++)     rev[i] = (rev[i >> 1]>>1)|((i&1)<<(len-1));
        fft(a, 1), fft(b, 1);
        for (int i = 0; i < limit; i ++) a[i] = a[i] * b[i];
        fft(a, -1);
        int t = n + m;
        for (int i = 0; i <=n + m || sum[i] != 0 ; i ++) {
            int x = (int)(a[i].x / limit + 0.5);
            sum[i] += x;
            sum[i + 1] += sum[i]/10;
            sum[i] %= 10;
            t = i;
        }
        bool f = 1;
        bool co = 0;
        for (int i = t; i  >= 0; i --) {
            if (f && sum[i] ==0)continue;
            f = 0;
            cout << sum[i];
        }
        if (f)cout << 0;
        cout << endl;
        clear();
    }
}
signed main() {
   ll t = 1;//cin >> t;
   while (t--) {
      solve();
   }
}

FFT

上一篇:栈与队列


下一篇:Adaptive Control Strategies for Interlimb Coordination in Legged Robots: A Review