【叠个甲：内容仅供娱乐，抱着看乐子的心态看即可】

把两个数看成系数多项式

例一：123→3+2x+1x² (系数 [3,2,1]，x 代表 10 的幂)

例二：45→5+4x (系数 [5,4])

众所周知，两数相加 = 多项式系数对应相加

例：123+45→(3+5)+(2+4) x+1x²→8+6x+1x² 对应 168

正常直接加系数时间复杂度为 O(N)，但我想想出来一个比 O(N) 更low的代码，于是我想到了 FFT：

#include <bits/stdc++.h>
#define int long long
using namespace std; using vi = vector <int>; 
using db = double; using cd = complex<double>;
const db PI = acos(-1);

void fft(vector<cd>& a, bool _) {
    int n = a.size();
    if (n <= 1) return;
    vector<cd> a0(n / 2), a1(n / 2);
    for (int i = 0; 2 * i < n; ++i) a0[i] = a[2 * i], a1[i] = a[2 * i + 1];
    fft(a0, _); fft(a1, _);
    db ang = 2 * PI / n * (_ ? -1 : 1);
    cd w(1), wn(cos(ang), sin(ang));
    for (int i = 0; 2 * i < n; ++i) {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        if (_) a[i] /= 2, a[i + n / 2] /= 2;
        w *= wn;
    }
}

vi str_(const string& s) {
    vi res;
    for (auto it = s.rbegin(); it != s.rend(); ++it) res.push_back(*it - '0');
    return res;
}

string _str(vi& cf) {
    int c = 0;
    for (int i = 0; i < cf.size(); ++i) {
        int t = cf[i] + c; cf[i] = t % 10; c = t / 10;
    }
    while (c > 0) cf.push_back(c % 10), c /= 10;
    while (cf.size() > 1 && cf.back() == 0) cf.pop_back();
    string res;
    for (auto it = cf.rbegin(); it != cf.rend(); ++it) res += (*it + '0');
    return res;
}

string fft_add(const string& a_str, const string& b_str) {
    vi a_cf = str_(a_str), b_cf = str_(b_str);
    int n = 1;
    int max_len = max(a_cf.size(), b_cf.size());
    while (n < max_len) n <<= 1;
    n <<= 1;  
    vector<cd> a_fft(n), b_fft(n);
    for (int i = 0; i < a_cf.size(); ++i) a_fft[i] = a_cf[i];
    for (int i = 0; i < b_cf.size(); ++i) b_fft[i] = b_cf[i];
    fft(a_fft, false), fft(b_fft, false);
    vector<cd> c_fft(n);
    for (int i = 0; i < n; ++i) c_fft[i] = a_fft[i] + b_fft[i];
    fft(c_fft, true);
    vi c_cf(n);
    for (int i = 0; i < n; ++i) c_cf[i] = round(c_fft[i].real());
    return _str(c_cf);
}

signed main() {
    ios::sync_with_stdio (false); cin.tie (NULL); 
    cin.rdbuf() -> pubsetbuf (NULL, 1 << 20);
    cout.rdbuf() -> pubsetbuf (NULL, 1 << 20);
    string a, b; cin >> a >> b;
    cout << fft_add(a, b);
}

时间复杂度：O(?)

但这还是不够，我们可以继续优化为 O(?)

于是乎我们可以放弃 FFT，改用离散傅里叶变换，也就是 DFT

算 DFT 和 逆 DFT，其复杂度就达到了 O(?)

计算每个 A[k] 要遍历 n 个 a[j] ，做 n 次复数乘法和加法，要算 n 个 A[k]

逆离散傅里叶变换（IDFT）的定义类似，只是旋转因子变为 Wₙ^{-jk} ，最后除以 n

为了达到 O(?) 的时间复杂度，我将原代码中的 FFT 替换为 DFT/IDFT：

#include <bits/stdc++.h>
#define int long long
using namespace std; 
using vi = vector <int>; using db = double; using cd = complex<double>;
const db PI = acos(-1);
void dft(vector<cd>& a, bool _) {
    int n = a.size();
    vector<cd> res(n);
    db theta = 2 * PI / n * (_ ? 1 : -1); 
    for (int k = 0; k < n; ++k) {  
        for (int j = 0; j < n; ++j) {  
            db ang = theta * j * k;
            cd w(cos(ang), sin(ang));  
            res[k] += a[j] * w;
        }
        if (_) res[k] /= n;  
    }
    a.swap(res);
}

vi str_(const string& s) {
    vi res;
    for (auto it = s.rbegin(); it != s.rend(); ++it) res.push_back(*it - '0');
    return res;
}

string _str(vi& cf) {
    int c = 0;
    for (int i = 0; i < cf.size(); ++i) {
        int t = cf[i] + c;
        cf[i] = t % 10; c = t / 10;
    }
    while (c > 0) cf.push_back(c % 10), c /= 10;
    while (cf.size() > 1 && cf.back() == 0) cf.pop_back();
    string res;
    for (auto it = cf.rbegin(); it != cf.rend(); ++it) res += (*it + '0');
    return res;
}

string dft_add(const string& a_str, const string& b_str) {
    vi a_cf = str_(a_str), b_cf = str_(b_str);
    int n = max(a_cf.size(), b_cf.size());  
    a_cf.resize(n, 0); 
    b_cf.resize(n, 0);
    vector<cd> a_dft(n), b_dft(n);
    for (int i = 0; i < n; ++i) a_dft[i] = a_cf[i], b_dft[i] = b_cf[i];
    dft(a_dft, false);  
    dft(b_dft, false);
    vector<cd> c_dft(n);
    for (int i = 0; i < n; ++i) c_dft[i] = a_dft[i] + b_dft[i]; 
    dft(c_dft, true);  
    vi c_cf(n);
    for (int i = 0; i < n; ++i) c_cf[i] = round(c_dft[i].real());
    return _str(c_cf);
}

signed main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    string a, b; cin >> a >> b;
    cout << dft_add(a, b);
}