又一A+B 神秘时间N方做法

肥膘肉

2025-08-27 21:03:33

发布于：湖南

27阅读

0回复

0点赞

【先叠个甲：内容纯属乱搞仅供娱乐，实测在洛谷会Unaccepted，抱着看乐子的心态看就行】

把两个数看成系数多项式

例一： $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)$ 更牛逼的代码，于是我想到了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(N \log N)$

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

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

直接算 DFT 和逆 DFT，其复杂度就达到了 $O(N²)$

离散傅里叶变换（DFT）的定义如下：

对长度为 $n$ 的序列 $a[0..n-1]$ ，其 DFT 结果 $A[0..n-1]$ 满足：

$A[k] = \sum_{j=0}^{n-1} a[j] \cdot W_n^{jk} \quad (0 \leq k < n)$

其中：

$W_n = e^{-2\pi i / n}$

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

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

为了达到 $O(N²)$ 的时间复杂度，我将原代码中的 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);
}