HDU 1402 – A * B Problem Plus [FFT模板]

Link

传送门

Problem

Calculate A * B.

Each line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000.

For each case, output A * B in one line.

Maen

计算A*B,A和B每个数最长50000位。

Analysis

直接算肯定不行了,要NlogN。直接上FFT模板好了。

脑子太笨,暂时还理解不了快速傅里叶变换…….

Code

#include <bits/stdc++.h>
using namespace std;
typedef complex<double> Complex;

const int MAXN = 200010;
const double PI = acos(-1.0);
char s1[MAXN], s2[MAXN];
Complex A[MAXN], B[MAXN];
int len1, len2, ans[MAXN];

void bulid(Complex _P[], Complex P[], int n, int m, int curr, int &cnt) {
    if (m == n) _P[curr] = P[cnt++];
    else {
        bulid(_P, P, n, m * 2, curr, cnt);
        bulid(_P, P, n, m * 2, curr + m, cnt);
    }
    return;
}

/**
 * P 需要进行DFT变换的数据
 * n 数据长度(2的整数次幂)
 * oper 1(正变换), -1(负变换)
 */
void FFT(Complex P[], int n, int oper) {
    static Complex _P[MAXN];
    int cnt = 0;
    bulid(_P, P, n, 1, 0, cnt);
    copy(_P, _P + n, P);
    for (int d = 0; (1 << d) < n; d++) {
        int m = 1 << d;
        int m2 = m * 2;
        double p0 = PI / m * oper;
        Complex unit_p0 = Complex(cos(p0), sin(p0));
        for (int i = 0; i < n; i += m2) {
            Complex unit = 1;
            for (int j = 0; j < m; ++j) {
                Complex &P1 = P[i + j + m], &P2 = P[i + j];
                Complex t = unit * P1;
                P1 = P2 - t;
                P2 = P2 + t;
                unit = unit * unit_p0;
            }
        }
    }
    if (oper == -1) {
        for (int i = 0; i < n; ++i)
            P[i] = Complex(P[i].real() / n, P[i].imag());
    }
}

int main() {
    while (~scanf("%s %s", s1, s2)) {
        memset(ans, 0, sizeof(ans));
        len1 = strlen(s1);
        len2 = strlen(s2);
        int len = 1;
        while (len < (2 * len1) || len < (2 * len2))
            len <<= 1;
        for (int i = 0; i < len1; ++i)
            A[i] = Complex(double(s1[len1 - i - 1] - '0'), 0.0);
        for (int i = len1; i < len; ++i)
            A[i] = Complex(0.0, 0.0);
        for (int i = 0; i < len2; ++i)
            B[i] = Complex(double(s2[len2 - i - 1] - '0'), 0.0);
        for (int i = len2; i < len; ++i)
            B[i] = Complex(0.0, 0.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] = (int)round(A[i].real());
        for (int i = 0; i < len; ++i) {
            ans[i + 1] += ans[i] / 10;
            ans[i] %= 10;
        }
        len = len1 + len2;
        while (!ans[len] && len > 0) len--;
        for (int i = len; i >= 0; --i)
            putchar((ans[i] + '0'));
        putchar('\n');
    }
    return 0;
}

欢迎留言