代码

#pragma GCC optimize("O3,unroll-loops,omit-frame-pointer")
#pragma GCC target("sse2")

#include <math.h>
#include <stdio.h>

struct Complex {
    double r, i;
};

enum { FFT_N = 8192, HALF = FFT_N / 2, BASE = 1000 };

static Complex values[FFT_N];
static Complex roots[HALF];
static char input[20032];
static char output[20032];
static long long coefficient[FFT_N];

static inline Complex multiply(Complex a, Complex b) {
    return {a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r};
}

static void initialize_roots() {
    const Complex step = {
        0.99999970586288221916, 0.00076699031874270452694
    };
    roots[0] = {1.0, 0.0};
    for (unsigned i = 1; i < HALF; ++i)
        roots[i] = multiply(roots[i - 1], step);
}

static void fft(Complex *a, bool invert) {
    for (unsigned i = 1, j = 0; i < FFT_N; ++i) {
        unsigned bit = FFT_N >> 1;
        while (j & bit) {
            j ^= bit;
            bit >>= 1;
        }
        j ^= bit;
        if (i < j) {
            Complex t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    for (unsigned length = 2; length <= FFT_N; length <<= 1) {
        unsigned half = length >> 1;
        unsigned stride = FFT_N / length;
        for (unsigned block = 0; block < FFT_N; block += length) {
            for (unsigned j = 0; j < half; ++j) {
                Complex u = a[block + j];
                Complex w = roots[j * stride];
                if (invert) w.i = -w.i;
                Complex v = multiply(a[block + j + half], w);
                a[block + j] = {u.r + v.r, u.i + v.i};
                a[block + j + half] = {u.r - v.r, u.i - v.i};
            }
        }
    }
    if (invert) {
        const double scale = 1.0 / FFT_N;
        for (unsigned i = 0; i < FFT_N; ++i) {
            a[i].r *= scale;
            a[i].i *= scale;
        }
    }
}

static unsigned parse_limbs(const char *s, unsigned length, bool imaginary) {
    unsigned count = 0;
    while (length) {
        unsigned begin = length >= 3 ? length - 3 : 0;
        unsigned value = 0;
        for (unsigned i = begin; i < length; ++i)
            value = value * 10 + (unsigned)(s[i] - '0');
        if (imaginary)
            values[count].i = value;
        else
            values[count].r = value;
        ++count;
        length = begin;
    }
    return count;
}

int main() {
    size_t bytes = fread(input, 1, sizeof(input), stdin);
    unsigned first_length = 0;
    while (first_length < bytes && input[first_length] >= '0' && input[first_length] <= '9')
        ++first_length;
    unsigned second_start = first_length;
    while (second_start < bytes && (input[second_start] < '0' || input[second_start] > '9'))
        ++second_start;
    unsigned second_length = 0;
    while (second_start + second_length < bytes && input[second_start + second_length] >= '0' && input[second_start + second_length] <= '9')
        ++second_length;

    unsigned na = parse_limbs(input, first_length, false);
    unsigned nb = parse_limbs(input + second_start, second_length, true);
    if ((na == 1 && values[0].r == 0.0) || (nb == 1 && values[0].i == 0.0)) {
        fwrite("0\n", 1, 2, stdout);
        return 0;
    }

    initialize_roots();
    fft(values, false);
    values[0] = {values[0].r * values[0].i, 0.0};
    values[HALF] = {values[HALF].r * values[HALF].i, 0.0};
    for (unsigned k = 1; k < HALF; ++k) {
        unsigned j = FFT_N - k;
        Complex f = values[k];
        Complex g = {values[j].r, -values[j].i};
        Complex av = {(f.r + g.r) * 0.5, (f.i + g.i) * 0.5};
        Complex bv = {(f.i - g.i) * 0.5, (g.r - f.r) * 0.5};
        Complex product = multiply(av, bv);
        values[k] = product;
        values[j] = {product.r, -product.i};
    }
    fft(values, true);

    unsigned nc = na + nb;
    long long carry = 0;
    for (unsigned i = 0; i < nc; ++i) {
        long long value = (long long)(values[i].r + 0.5) + carry;
        coefficient[i] = value % BASE;
        carry = value / BASE;
    }
    while (carry) {
        coefficient[nc++] = carry % BASE;
        carry /= BASE;
    }
    while (nc > 1 && coefficient[nc - 1] == 0) --nc;

    char *p = output;
    long long top = coefficient[--nc];
    char reverse[24];
    unsigned digits = 0;
    do {
        reverse[digits++] = (char)('0' + top % 10);
        top /= 10;
    } while (top);
    while (digits) *p++ = reverse[--digits];
    while (nc) {
        unsigned value = (unsigned)coefficient[--nc];
        *p++ = (char)('0' + value / 100);
        *p++ = (char)('0' + value / 10 % 10);
        *p++ = (char)('0' + value % 10);
    }
    *p++ = '\n';
    fwrite(output, 1, (size_t)(p - output), stdout);
    return 0;
}

评测结果