题目地址：洛谷：【P1919】【模板】A*B Problem升级版（FFT快速傅里叶） – 洛谷、BZOJ：Problem 2179. — FFT快速傅立叶
写这题只是为了证明我今天写了两个题。无视即可。

题目描述

给出两个n位10进制整数x和y，你需要计算x*y。

输入输出格式

输入格式：
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。

输出格式：
输出一行，即x*y的结果。（注意判断前导0）

输入输出样例

输入样例#1：

1
3
4

输出样例#1：

12

说明

数据范围：n<=60000

题解

实际上乘法是在对每一位做卷积。倒序读进去，FFT一下，倒序输出即可。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline int readsingle() {
    char c = fgc();
    while(c < '0' || c > '9') c = fgc();
    return c - '0';
}

const int MAXN = 1 << 17;
const double PI = acos(-1);

struct Complex {
    double real, imag;
    Complex(double real = 0, double imag = 0) : real(real), imag(imag) {}
    inline Complex operator+(const Complex &rhs) const {
        return Complex(real + rhs.real, imag + rhs.imag);
    }
    inline Complex operator-(const Complex &rhs) const {
        return Complex(real - rhs.real, imag - rhs.imag);
    }
    inline Complex operator*(const Complex &rhs) const {
        return Complex(real * rhs.real - imag * rhs.imag, real * rhs.imag + imag * rhs.real);
    }
    inline Complex& operator*=(const Complex &rhs) {
        Complex old = *this;
        real = old.real * rhs.real - old.imag * rhs.imag;
        imag = old.real * rhs.imag + old.imag * rhs.real;
        return *this;
    }
};

int n, m, len, rev[MAXN], c[MAXN];
Complex a[MAXN], b[MAXN];

inline void fft(Complex *arr, int f) {
    for(int i = 0; i < n; i++) {
        if(i < rev[i]) std::swap(arr[i], arr[rev[i]]);
    }
    for(int i = 1; i < n; i <<= 1) {
        Complex wn(cos(PI / i), f * sin(PI / i));
        for(int j = 0; j < n; j += i << 1) {
            Complex w(1, 0);
            for(int k = 0; k < i; k++) {
                Complex x = arr[j + k], y = w * arr[j + k + i];
                arr[j + k] = x + y;
                arr[j + k + i] = x - y;
                w *= wn;
            }
        }
    }
}

int main() {
    n = readint() - 1;
    for(int i = 0; i <= n; i++) {
        a[n - i].real = readsingle();
    }
    for(int i = 0; i <= n; i++) {
        b[n - i].real = readsingle();
    }
    m = n << 1;
    for(n = 1; n <= m; n <<= 1) len++;
    for(int i = 0; i < n; i++) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
    }
    fft(a, 1);
    fft(b, 1);
    for(int i = 0; i <= n; i++) {
        a[i] *= b[i];
    }
    fft(a, -1);
    for(int i = 0; i <= m; i++) {
        c[i] = int(a[i].real / n + 0.5);
    }
    for(int i = 0; i <= m; i++) {
        if(c[i] >= 10) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
            if(i == m) m++;
        }
    }
    bool flag = true;
    for(int i = m; i >= 0; i--) {
        if(flag && c[i]) flag = false;
        if(!flag) printf("%d", c[i]);
    }
    return 0;
}