# [A+B · 当人类群星闪耀时](https://a-plus-b.pages.dev/)

> _谨以此文献给所有在 A+B 问题上"过度设计"的先驱们_

---

## 序章 · 一道题，万种解法

在无数 OJ 的角落里，有一道题，它叫 **P1001 A+B Problem**。

它只有一行需求：输入两个数，输出它们的和。

勇士们拿起算法的武器，向一座看似坚固的"简单"堡垒发起了冲锋。

**这是一部人类群星闪耀史。**

---

## 第一章 · 数据结构篇

### LCT · 情感的波折

有人说，程序是冰冷的。**LCT 哥**不同意。

他建了两个节点，让它们**相识**——`connect(A, B)`。  
然后**分手**——`cut(A, B)`。  
最后**复合**——`connect(A, B)`。

在经历了完整的情感波折后，他查询了它们的"爱情结晶"——路径和。

**两百行代码，只为一个浪漫的加法。**

> "动态树：我用 200 行代码，证明了我能算 1+1。"

```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct node
{
    int data,rev,sum;
    node *son[2],*pre;
    bool judge();
    bool isroot();
    void pushdown();
    void update();
    void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x)
{
    node *now=lct+ ++top;
    now->data=x;
    now->pre=now->son[1]=now->son[0]=lct;
    now->sum=0;
    now->rev=0;
    return now;
}
bool node::judge(){return pre->son[1]==this;}
bool node::isroot()
{
    if(pre==lct)return true;
    return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown()
{
    if(this==lct||!rev)return;
    swap(son[0],son[1]);
    son[0]->rev^=1;
    son[1]->rev^=1;
    rev=0;
}
void node::update(){sum=son[1]->sum+son[0]->sum+data;}
void node::setson(node *child,int lr)
{
    this->pushdown();
    child->pre=this;
    son[lr]=child;
    this->update();
}
void rotate(node *now)
{
    node *father=now->pre,*grandfa=father->pre;
    if(!father->isroot()) grandfa->pushdown();
    father->pushdown();now->pushdown();
    int lr=now->judge();
    father->setson(now->son[lr^1],lr);
    if(father->isroot()) now->pre=grandfa;
    else grandfa->setson(now,father->judge());
    now->setson(father,lr^1);
    father->update();now->update();
    if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
    if(now->isroot())return;
    for(;!now->isroot();rotate(now))
    if(!now->pre->isroot())
    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
    node *last=lct;
    for(;now!=lct;last=now,now=now->pre)
    {
        splay(now);
        now->setson(last,1);
    }
    return last;
}
void changeroot(node *now)
{
    access(now)->rev^=1;
    splay(now);
}
void connect(node *x,node *y)
{
    changeroot(x);
    x->pre=y;
    access(x);
}
void cut(node *x,node *y)
{
    changeroot(x);
    access(y);
    splay(x);
    x->pushdown();
    x->son[1]=y->pre=lct;
    x->update();
}
int query(node *x,node *y)
{
    changeroot(x);
    node *now=access(y);
    return now->sum;
}
int main()
{
    scanf("%d%d",&a,&b);
    node *A=getnew(a);
    node *B=getnew(b);
        connect(A,B);
        cut(A,B);
        connect(A,B);
    printf("%d\n",query(A,B));
    return 0;
}
```

---

### 线段树 · 集装箱里的芝麻

**线段树哥**说："我的代码要有工业级的冗余。"

于是他开了一棵 4×1e5 的线段树，建在只有 1 个元素的数组上。

他用**标记永久化**做区间加，虽然只加了一次。

他传了 `tags` 参数累加路径标记，虽然路径只有一层。

**50 倍的常数，只为 100 分的尊严。**

> "用集装箱存一颗芝麻，然后骄傲地说：看，我的芝麻有专属仓库！"

```cpp
#include <cstdio>
#define mid L + (R-L >> 1)
const int maxn = 1e5+5;
int n, a[maxn], m;
int sl, sr, add;
struct segtree{
    int sum[maxn<<2], tag[maxn<<2];
    inline int lc(int o){return o<<1;}
    inline int rc(int o){return o<<1|1;}
    void build(int o, int L, int R){
        if(L == R){sum[o] = a[L];return;}
        int M = mid;
        build(lc(o), L, M);
        build(rc(o), M+1, R);
        sum[o] = sum[lc(o)] + sum[rc(o)];
    }
    void maintain(int o, int L, int R){
        if(R>L){
            sum[o] = sum[lc(o)] + sum[rc(o)];
            sum[o] += tag[o] * (R-L+1);
        } else {
            sum[o] += tag[o];
            tag[o] = 0;
        }
    }
    void updata(int o, int L, int R){
        if(sl <= L && R <= sr)tag[o] += add;
        else{
            int M = mid;
            if(sl <= M)updata(lc(o), L, M);
            if(sr > M)updata(rc(o), M+1, R);
        }
        maintain(o, L, R);
    }
    int query(int o, int L, int R, int tags){
        if(sl <= L && R <= sr)return sum[o] + tags * (R-L+1);
        else {
            int M = mid, res = 0;
            if(sl <= M)res += query(lc(o), L, M, tags+tag[o]);
            if(sr > M)res += query(rc(o), M+1, R, tags+tag[o]);
            return res;
        }
    }
} sol;
signed main(){
    n = 1;
    int a, b;
    scanf("%d%d", &a, &b);
    sol.build(1, 1, n);
    add=a; sl=1; sr=1;
    sol.updata(1, 1, 1);
    add=b;
    sol.updata(1, 1, 1);
    printf("%d\n", sol.query(1, 1, n, 0));
    return 0;
}
```

---

### 树状数组 · 五十万格储物柜

**树状数组哥**更狠。

他开了 500005 个空间，用 lowbit 维护 1 个数的前缀和。

只有 1 个数，但数组要开到 50 万。

**空着 499999 个格子，是一种态度。**

> "邻居问：你家储物柜为什么空着 499999 格？"

```cpp
#include <iostream>
using namespace std;
const int n = 1;
int a, b;
int c[500005];
inline int lowbit(int x){
    return x & (-x);
}
inline int sum(int x){
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    ans+=c[i];
    return ans;
}
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))
    c[i]+=y;
}
int main(){
    cin>>a>>b;
    add(1, a); add(1, b);
    printf("%d\n", sum(1));
    return 0;
}
```

---

### Splay · 翻转的哲学

**Splay 哥**说："加法满足交换律。"

然后他用 100 行代码实现了 Splay，建了 4 个节点。

把序列 `[a, b]` 翻转成 `[b, a]`。

最后查询区间和——`a+b` 还是 `a+b`。

**他证明了：翻转不影响结果，正如爱不影响加法。**

> "翻转序列是为了证明加法交换律，数学老师哭了。"

```cpp
#include <bits/stdc++.h>
#define ll long long
#define N 100000
using namespace std;
int sz[N], rev[N], tag[N], sum[N], ch[N][2], fa[N], val[N];
int n, m, rt, x;
void push_up(int x){
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    sum[x] = sum[ch[x][1]] + sum[ch[x][0]] + val[x];
}
void push_down(int x){
    if(rev[x]){
        swap(ch[x][0], ch[x][1]);
        if(ch[x][1]) rev[ch[x][1]] ^= 1;
        if(ch[x][0]) rev[ch[x][0]] ^= 1;
        rev[x] = 0;
    }
    if(tag[x]){
        if(ch[x][1]) tag[ch[x][1]] += tag[x], sum[ch[x][1]] += tag[x];
        if(ch[x][0]) tag[ch[x][0]] += tag[x], sum[ch[x][0]] += tag[x];
        tag[x] = 0;
    }
}
void rotate(int x, int &k){
    int y = fa[x], z = fa[fa[x]];
    int kind = ch[y][1] == x;
    if(y == k) k = x;
    else ch[z][ch[z][1]==y] = x;
    fa[x] = z; fa[y] = x; fa[ch[x][!kind]] = y;
    ch[y][kind] = ch[x][!kind]; ch[x][!kind] = y;
    push_up(y); push_up(x);
}
void splay(int x, int &k){
    while(x != k){
        int y = fa[x], z = fa[fa[x]];
        if(y != k) if(ch[y][1] == x ^ ch[z][1] == y) rotate(x, k);
        else rotate(y, k);
        rotate(x, k);
    }
}
int kth(int x, int k){
    push_down(x);
    int r = sz[ch[x][0]]+1;
    if(k == r) return x;
    if(k < r) return kth(ch[x][0], k);
    else return kth(ch[x][1], k-r);
}
void split(int l, int r){
    int x = kth(rt, l), y = kth(rt, r+2);
    splay(x, rt); splay(y, ch[rt][1]);
}
void rever(int l, int r){
    split(l, r);
    rev[ch[ch[rt][1]][0]] ^= 1;
}
void add(int l, int r, int v){
    split(l, r);
    tag[ch[ch[rt][1]][0]] += v;
    val[ch[ch[rt][1]][0]] += v;
    push_up(ch[ch[rt][1]][0]);
}
int build(int l, int r, int f){
    if(l > r) return 0;
    if(l == r){
        fa[l] = f;
        sz[l] = 1;
        return l;
    }
    int mid = l + r >> 1;
    ch[mid][0] = build(l, mid-1, mid);
    ch[mid][1] = build(mid+1, r, mid);
    fa[mid] = f;
    push_up(mid);
    return mid;
}
int asksum(int l, int r){
    split(l, r);
    return sum[ch[ch[rt][1]][0]];
}
int main(){
    n = 2;
    rt = build(1, n+2, 0);
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        add(i, i, x);
    }
    rever(1, n);
    printf("%d\n", asksum(1, n));
    return 0;
}
```

---

### Treap · 把 a 拆成 a 个 1

**Treap 哥**说："插入 a 个 1，插入 b 个 1，然后查 1 的排名。"

于是循环跑了 a+b 次，插了 200 万个 1。

树高 20，旋转 4000 万次，CPU 风扇狂转。

**最后输出 2000000。**

> "算个加法用了 4000 万次旋转，隔壁做渲染的以为我在跑 3D 建模。"

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int read(){int a = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9'){a = a * 10 + ch - '0'; ch = getchar(); }
    return a * f;}
inline void write(int x){if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10); putchar(x % 10 + '0'); }
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
struct Treap{
    int ls, rs;
    int val, rnd;
    int siz, cnt;
}tr[N];
int tot = 0;
inline void Updata(int x){ tr[x].siz = tr[tr[x].ls].siz
    + tr[tr[x].rs].siz + tr[x].cnt; }
inline int New(int x){
    tr[++tot].val = x;
    tr[tot].rnd = rand();
    tr[tot].siz = tr[tot].cnt = 1;
    return tot;
}
int root = 0;
inline void Build(){
    New(-INF), New(INF);
    root = 1;
    tr[root].rs = 2;
    Updata(root);
}
inline void zig(int &y){
    int x = tr[y].ls;
    tr[y].ls = tr[x].rs;
    tr[x].rs = y;
    y = x;
    Updata(tr[y].rs);
    Updata(y);
}
inline void zag(int &y){
    int x = tr[y].rs;
    tr[y].rs = tr[x].ls;
    tr[x].ls = y;
    y = x;
    Updata(tr[y].ls);
    Updata(y);
}
inline void Insert(int &x, int val){
    if(!x){
        x = New(val);
        return ;
    }
    if(tr[x].val == val){
        ++tr[x].cnt;
        Updata(x);
        return ;
    }
    if(val < tr[x].val){
        Insert(tr[x].ls, val);
        if(tr[x].rnd < tr[tr[x].ls].rnd) zig(x);
    }
    else{
        Insert(tr[x].rs, val);
        if(tr[x].rnd < tr[tr[x].rs].rnd) zag(x);
    }
    Updata(x);
}
inline void Delete(int &x, int val){
    if(!x) return ;
    if(tr[x].val == val){
        if(tr[x].cnt > 1){
            --tr[x].cnt;
            Updata(x);
            return ;
        }
        if(!tr[x].ls && !tr[x].rs){
            x = 0;
            return ;
        }
        else if(!tr[x].rs || (tr[x].ls && tr[tr[x].ls].rnd > tr[tr[x].rs].rnd)){
            zig(x);
            Delete(tr[x].rs, val);
        }
        else{
            zag(x);
            Delete(tr[x].ls, val);
        }
    }
    else if(val < tr[x].val) Delete(tr[x].ls, val);
    else Delete(tr[x].rs, val);
    Updata(x);
}
inline int get_rank(int x, int val){
    if(!x) return 0;
    if(tr[x].val == val) return tr[tr[x].ls].siz + tr[x].cnt;
    if(val < tr[x].val) return get_rank(tr[x].ls, val);
    return get_rank(tr[x].rs, val) + tr[tr[x].ls].siz + tr[x].cnt;
}
inline int get_val(int x, int rank){
    if(!x) return INF;
    if(tr[tr[x].ls].siz >= rank) return get_val(tr[x].ls, rank);
    if(tr[tr[x].ls].siz + tr[x].cnt >= rank) return tr[x].val;
    return get_val(tr[x].rs, rank - tr[tr[x].ls].siz - tr[x].cnt);
}
inline int get_pre(int x, int val){
    int ans = 1;
    while(x){
        if(val == tr[x].val){
            if(tr[x].ls > 0){
                x = tr[x].ls;
                while(tr[x].rs > 0) x = tr[x].rs;
                ans = x;
            }
            break;
        }
        if(val > tr[x].val && tr[x].val > tr[ans].val) ans = x;
        x = val < tr[x].val ? tr[x].ls : tr[x].rs;
    }
    return tr[ans].val;
}
inline int get_last(int x, int val){
    int ans = 2;
    while(x){
        if(val == tr[x].val){
            if(tr[x].rs > 0){
                x = tr[x].rs;
                while(tr[x].ls > 0) x = tr[x].ls;
                ans = x;
            }
            break;
        }
        if(val < tr[x].val && tr[x].val < tr[ans].val) ans = x;
        x = val < tr[x].val ? tr[x].ls : tr[x].rs;
    }
    return tr[ans].val;
}
int main(){
    srand(time(0));
    int a = read(), b = read();
    for(int i = 1; i <= a; i++) {
        Insert(root, 1);
    }
    for(int i = 1; i <= b; i++) {
        Insert(root, 1);
    }
    write(get_rank(root, 1));
    return 0;
}
```

---

## 第二章 · 图论篇

### Dijkstra · 导航软件的噩梦

**Dijkstra 哥**建了一张图：0→1（边权 a），1→2（边权 b）。

然后跑了一遍最短路算法：松弛、入队、出队、再松弛。

最后郑重宣布：**从 0 到 2 的最短路径是 a+b。**

导航软件听了一下自己的光荣事迹，默默把自己卸载了。

> "导航软件：我这就下岗？"

```cpp
#include<bits/stdc++.h>
#define int unsigned long long
#define code using
#define by namespace
#define XWC std;
#define f first
code by XWC
const int N=1e5+10;
struct edge{
    int v,w;
};
struct node{
    int dis,u;
    bool operator>(const node& a) const {return dis>a.dis;}
};
vector<edge> e[N];
int dis[N],vis[N];
int u,v,w;
int qq[10];
priority_queue<node,vector<node>,greater<node> > q;
void Dijkstra(int n,int s){
    for(int i=0;i<=n;i++) dis[i]=8e18+10;
    for(int i=0;i<=n;i++) vis[i]=0;
    dis[s]=0;
    while(!q.empty()) q.pop();
    q.push({0,s});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}
int n=2,m=1,a,b;
signed main(){
    n=2,m=1;
    cin>>a>>b;
    e[n/2].push_back({n,a+b});
    Dijkstra(n,1);
    cout<<dis[n];
    return 0;
}
```

---

### Kruskal · INF 的尊严

**Kruskal 哥**更离谱。

他建了三条边：a、b、INF。

然后跑了最小生成树——选了 a 和 b，INF 被冷落。

**那条 INF 边，从出生就注定不被选择。**

> "边：我不要面子的吗？"

```cpp
#include <cstdio>
#include <algorithm>
#define INF 2140000000
using namespace std;
struct tree{int x,y,t;}a[10];
bool cmp(const tree&a,const tree&b){return a.t<b.t;}
int f[11],i,j,k,n,m,x,y,t,ans;
int root(int x){if (f[x]==x) return x;f[x]=root(f[x]);return f[x];}
int main(){
    for (i=1;i<=10;i++) f[i]=i;
    for (i=1;i<=2;i++){
        scanf("%d",&a[i].t);
        a[i].x=i+1;a[i].y=1;k++;
    }
    a[++k].x=1;a[k].y=3,a[k].t=INF;
    sort(a+1,a+1+k,cmp);
    for (i=1;i<=k;i++){
        x=root(a[i].x);y=root(a[i].y);
        if (x!=y) f[x]=y,ans+=a[i].t;
    }
    printf("%d\n",ans);
}
```

---

## 第三章 · 数学篇

### 完全平方 · 高精度的浪漫

**完全平方哥**说："我们知道 (a+b)² = a² + b² + 2ab。"

所以他写了 150 行高精度：加法、减法、乘法、除法、开根号、比较大小。

然后算 1²+2²+2×1×2=9，开根号得 3。

**数学老师看了直摇头："公式不是这么用的。"**

> "少年，公式是让你算展开，不是让你绕路的。"

```cpp
#include <bits/stdc++.h>
using namespace std;
string qf (string a)
{
    if (a[0] == '-') return a.substr (1 , a.size () - 1);
    return "-" + a;
}
string operator - (string a) {return qf (a);}
string gjc (string a , string b)
{
    if (a[0] == '-' && b[0] == '-') return gjc (- a , - b);
    else if (a[0] == '-') return - gjc (- a , b);
    else if (b[0] == '-') return - gjc (a , - b);
    int ans[a.size () + b.size ()] = {};
    reverse (a.begin () , a.end ());
    reverse (b.begin () , b.end ());
    for (int i = 0;i < a.size ();i ++)
        for (int j = 0;j < b.size ();j ++)
            ans[i + j] += (a[i] - '0') * (b[j] - '0');
    for (int i = 0;i < a.size () + b.size ();i ++)
        if (ans[i] > 9)
        {
            int x = ans[i] % 10 , y = ans[i] / 10;
            ans[i] = x;
            ans[i + 1] += y;
        }
    string ans2 = "";
    for (int i = 1;i <= a.size () + b.size ();i ++)
        ans2 += (char) (ans[i - 1] + '0');
    if (ans2[ans2.size () - 1] == '0')
        ans2 = ans2.substr (0 , ans2.size () - 1);
    reverse (ans2.begin () , ans2.end ());
    return ans2;
}
string max (string a , string b)
{
    if (a[0] == '-' && b[0] == '-')
    {
        if (- max (- a , - b) == a) return b;
        return a;
    }
    else if (a[0] == '-') return b;
    else if (b[0] == '-') return a;
    else if (a.size () > b.size ()) return a;
    else if (a.size () < b.size ()) return b;
    else
    {
        for (int i = 0;i < a.size ();i ++)
            if (a[i] > b[i]) return a;
            else if (a[i] < b[i]) return b;
        return a;
    }
}
string min (string a , string b)
{
    if (max (a , b) == a) return b;
    return a;
}
string gjj (string a , string b);
string cut (string a , string b)
{
    if (a[0] == '-' && b[0] == '-') return cut (- b , - a);
    else if (a[0] == '-') return - gjj (- a , b);
    else if (b[0] == '-') return gjj (b , - a);
    else if (max (a , b) != a) return - cut (b , a);
    reverse (a.begin () , a.end ());
    reverse (b.begin () , b.end ());
    string ans = "";
    for (int i = 1;i <= a.size () + 1;i ++) ans += "0";
    for (int i = 0;i < b.size ();i ++) ans[i] += a[i] - b[i];
    for (int i = b.size ();i < a.size ();i ++) ans[i] = a[i];
    for (int i = 0;i < ans.size ();i ++)
        if (ans[i] < '0')
        {
            ans[i] += 10;
            ans[i + 1] -= 1;
        }
    while (ans.size () > 1 && ans[ans.size () - 1] == '0')
        ans = ans.substr (0 , ans.size () - 1);
    reverse (ans.begin () , ans.end ());
    return ans;
}
string gjj (string a , string b)
{
    if (a[0] == '-' && b[0] == '-') return - gjc (- a , - b);
    else if (a[0] == '-') return cut (b , - a);
    else if (b[0] == '-') return cut (a , - b);
    if (a.size () < b.size ()) swap (a , b);
    reverse (a.begin () , a.end ());
    reverse (b.begin () , b.end ());
    string ans = "";
    for (int i = 1;i <= a.size () + 1;i ++) ans += "0";
    for (int i = 0;i < b.size ();i ++) ans[i] += a[i] - '0' + b[i] - '0';
    for (int i = b.size ();i < a.size ();i ++) ans[i] = a[i];
    for (int i = 0;i < ans.size ();i ++)
        if (ans[i] > '9')
        {
            ans[i] -= 10;
            ans[i + 1] += 1;
        }
    if (ans[ans.size () - 1] == '0') ans = ans.substr (0 , ans.size () - 1);
    reverse (ans.begin () , ans.end ());
    return ans;
}
string dev (string b , int a)
{
    if (a < 0 && b[0] == '-') return dev (- b , - a);
    else if (a < 0) return - dev (b , - a);
    else if (b[0] == '-') return - dev (- b , a);
    while (a % 10 == 0 && b[b.size () - 1] == '0')
    {
        a /= 10;
        b = b.substr (0 , b.size () - 1);
    }
    string ans = "";
    int yu = 0;
    for (int i = 0;i < b.size ();i ++)
    {
        yu = yu * 10 + b[i] - '0';
        ans += yu / a + '0';
        yu %= a;
    }
    while (ans.size () > 1 && ans[0] == '0') ans = ans.substr (1);
    return ans;
}
string operator / (string a , int b) {return dev (a , b);}
string operator * (string a , string b) {return gjc (a , b);}
string operator + (string a , string b) {return gjj (a , b);}
string operator - (string a , string b) {return cut (a , b);}
string sqrt (string s)
{
    if (s == "0") return "0";
    if (s == "1") return "1";
    string l = "1" , r = "1" , ans , dan = "1";
    for (int i = 1;i < s.size () / 2;i ++) l += "0";
    for (int i = 1;i <= s.size () / 2 + 1;i ++) r += "0";
    while (max (l , r) == r)
    {
        string mid = (l + r) / 2;
        if (max (mid * mid , s) == s)
        {
            ans = mid;
            l = gjj (mid , dan);
        }
        else r = mid - dan;
    }
    return ans;
}
signed main ()
{
    string a , b , c = "2";
    cin >> a >> b;
    if (a[0] == '-' && b[0] == '-')
        cout << - sqrt (a * a + b * b + c * a * b);
    else if (a[0] == '-')
    {
        if (max (- a , b) == b) cout << sqrt (a * a + b * b + c * a * b);
        else cout << - sqrt (a * a + b * b + c * a * b);
    }
    else if (b[0] == '-')
    {
        if (max (- b , a) == a) cout << sqrt (a * a + b * b + c * a * b);
        else cout << - sqrt (a * a + b * b + c * a * b);
    }
    else cout << sqrt (a * a + b * b + c * a * b);
}
```

---

### FFT · 信号与系统的降维打击

**FFT哥**说："加法在时域是卷积，在频域是乘积！"

于是他手写了一个完整的高精度计算库——复数类、蝶形变换、压位存储、负数处理、借位优化，洋洋洒洒三百行。

为了算 1+2，他把两个数拆成 `BASE=100` 的位，做 FFT 到频域，点乘，逆变换，再进位。

高精度加法就这样被 FFT 加速到了 O(n log n)。

**FFT：我优化了高精度加法的复杂度。可是蝴蝶还没来得及扇翅膀，加法已经算完了。**

```cpp
#include<cmath>
#include<iostream>
#include<cstring>
const double PI=4*atan(1);
template<typename T>
void Swap(T &a,T &b){
	T c=a;
	a=b;
	b=c;
	return;
}
template<typename T>
T Max(const T &a,const T &b){
	return a<b?b:a;
}
typedef long long ll;
struct comp{
	double real,imag;
	comp operator+(const comp &x)const{
		return {real+x.real,imag+x.imag};
	}
	comp operator-(const comp &x)const{
		return {real-x.real,imag-x.imag};
	}
	comp operator*(const comp &x)const{
		return {real*x.real-imag*x.imag,real*x.imag+x.real*imag};
	}
	comp operator/(const unsigned &x)const{
		return {real/(double)x,imag/(double)x};
	}
};
void FFT(comp *f,unsigned n,int rev){
	for(unsigned i=1,j=n>>1,k;i<n-1;i++){
		if(i<j)
			Swap(f[i],f[j]);
		k=n>>1;
		while(j>=k){
			j-=k;
			k>>=1;
		}
		j+=k;
	}
	for(unsigned l=2;l<=n;l<<=1){
		double arg=2*PI*rev/l;
		comp wn={cos(arg),sin(arg)};
		for(unsigned i=0;i<n;i+=l){
			comp w={1,0};
			for(unsigned j=0;j<(l>>1);j++){
				comp f1=f[i+j];
				comp f2=f[i+j+(l>>1)];
				f[i+j]=f1+w*f2;
				f[i+j+(l>>1)]=f1-w*f2;
				w=w*wn;
			}
		}
	}
	if(!~rev)
		for(unsigned i=0;i<n;i++)
			f[i]=f[i]/n;
}
#define BASE 100
template<const unsigned Size>
class bigint{
private:
	unsigned len;
	int num[Size];
	void init(){
		memset(num,0,sizeof(num));
		len=1;
	}
	bool abs_greater_equal(const bigint &a)const{
		if(len!=a.len)
			return len>a.len;
		for(int i=len;i;i--)
			if(num[i]!=a.num[i])
				return num[i]>a.num[i];
		return 1;
	}
public:
	bigint(){
		init();
	}
	void get_num(std::string s){
		init();
		int f=0;
		unsigned slen=s.length();
		if(s[0]=='-')
			num[0]=f=1;
		len=0;
		unsigned temp=0,w=1;
		for(int i=slen-1;i>=f;i--){
			temp+=(s[i]^48)*w;
			w=(w<<1)+(w<<3);
			if(w==BASE||i==f){
				num[++len]=(int)temp;
				temp=0;
				w=1;
			}
		}
		if(temp||len==0)
			num[++len]=temp;
	}
	bool operator<(const bigint &a)const{
		if(num[0]&&!a.num[0])
			return 1;
		if(!num[0]&&a.num[0])
			return 0;
		if(num[0]){
			if(len!=a.len)
				return len>a.len;
			for(int i=len;i;i--)
				if(num[i]!=a.num[i])
					return num[i]>a.num[i];
		}
		else{
			if(len!=a.len)
				return len<a.len;
			for(int i=len;i;i--)
				if(num[i]!=a.num[i])
					return num[i]<a.num[i];
		}
		return 0;
	}
	bigint operator+(const bigint &a)const{
		bigint res;
		if(len==1&&num[1]==0){
			res=a;
			return res;
		}
		if(a.len==1&&a.num[1]==0){
			res=*this;
			return res;
		}
		if(num[0]==a.num[0]){
			res.num[0]=num[0];
			unsigned len_sum=1;
			while(len_sum<len+a.len)
				len_sum<<=1;
			comp *fa=new comp[len_sum]();
			comp *fb=new comp[len_sum]();
			for(unsigned i=0;i<len;i++)
				fa[i]={(double)num[i+1],0};
			for(unsigned i=0;i<a.len;i++)
				fb[i]={(double)a.num[i+1],0};
			FFT(fa,len_sum,1);
			FFT(fb,len_sum,1);
			for(unsigned i=0;i<len_sum;i++)
				fa[i]=fa[i]+fb[i];
			FFT(fa,len_sum,-1);
			res.len=Max(len,a.len);
			ll temp=0;
			for(unsigned i=0;i<res.len;i++){
				ll val=(ll)round(fa[i].real)+temp;
				res.num[i+1]=(int)(val%BASE);
				temp=val/BASE;
			}
			if(temp)
				res.num[++res.len]=temp;
			while(res.len>1&&res.num[res.len]==0)
				res.len--;
			delete[] fa;
			delete[] fb;
		}
		else{
			if(abs_greater_equal(a)){
				res.num[0]=num[0];
				unsigned len_sum=1;
				while(len_sum<len+a.len)
					len_sum<<=1;
				comp *fa=new comp[len_sum]();
				comp *fb=new comp[len_sum]();
				for(unsigned i=0;i<len;i++)
					fa[i]={(double)num[i+1],0};
				for(unsigned i=0;i<a.len;i++)
					fb[i]={(double)a.num[i+1],0};
				FFT(fa,len_sum,1);
				FFT(fb,len_sum,1);
				for(unsigned i=0;i<len_sum;i++)
					fa[i]=fa[i]-fb[i];
				FFT(fa,len_sum,-1);
				res.len=Max(len,a.len);
				ll temp=0;
				for(unsigned i=0;i<res.len;i++){
					ll val=(ll)round(fa[i].real)+temp;
					if(val<0){
						val+=BASE;
						temp=-1;
					}
					else
						temp=0;
					res.num[i+1]=(int)(val%BASE);
				}
				if(temp)
					res.num[++res.len]=temp;
				while(res.len>1&&res.num[res.len]==0)
					res.len--;
				delete[] fa;
				delete[] fb;
			}
			else{
				res.num[0]=a.num[0];
				unsigned len_sum=1;
				while(len_sum<len+a.len)
					len_sum<<=1;
				comp *fa=new comp[len_sum]();
				comp *fb=new comp[len_sum]();
				for(unsigned i=0;i<len;i++)
					fa[i]={(double)num[i+1],0};
				for(unsigned i=0;i<a.len;i++)
					fb[i]={(double)a.num[i+1],0};
				FFT(fa,len_sum,1);
				FFT(fb,len_sum,1);
				for(unsigned i=0;i<len_sum;i++)
					fa[i]=fb[i]-fa[i];
				FFT(fa,len_sum,-1);
				res.len=Max(len,a.len);
				ll temp=0;
				for(unsigned i=0;i<res.len;i++){
					ll val=(ll)round(fa[i].real)+temp;
					if(val<0){
						val+=BASE;
						temp=-1;
					}
					else
						temp=0;
					res.num[i+1]=(int)(val%BASE);
				}
				if(temp)
					res.num[++res.len]=temp;
				while(res.len>1&&res.num[res.len]==0)
					res.len--;
				delete[] fa;
				delete[] fb;
			}
			if(res.len==1&&res.num[1]==0)
				res.num[0]=0;
		}
		return res;
	}
	bigint operator*(const bigint &a)const{
		bigint res;
		if((len==1&&num[1]==0)||(a.len==1&&a.num[1]==0))
			return res;
		res.num[0]=num[0]^a.num[0];
		unsigned len_sum=1;
		while(len_sum<len+a.len)
			len_sum<<=1;
		comp *fa=new comp[len_sum]();
		comp *fb=new comp[len_sum]();
		for(unsigned i=0;i<len;i++)
			fa[i]={(double)num[i+1],0};
		for(unsigned i=0;i<a.len;i++)
			fb[i]={(double)a.num[i+1],0};
		FFT(fa,len_sum,1);
		FFT(fb,len_sum,1);
		for(unsigned i=0;i<len_sum;i++)
			fa[i]=fa[i]*fb[i];
		FFT(fa,len_sum,-1);
		res.len=len+a.len;
		ll temp=0;
		for(unsigned i=0;i<res.len;i++){
			ll val=(ll)(fa[i].real+0.5)+temp;
			res.num[i+1]=(int)(val%BASE);
			temp=val/BASE;
		}
		if(temp)
			res.num[++res.len]=temp;
		while(res.len>1&&res.num[res.len]==0)
			res.len--;
		delete[] fa;
		delete[] fb;
		return res;
	}
	void read(){
		init();
		std::string s;
		char ch=getchar();
		while(ch<'0'||ch>'9'){
			if(ch=='-')
				s.push_back('-');
			ch=getchar();
		}
		while(ch>='0'&&ch<='9'){
			s.push_back(ch);
			ch=getchar();
		}
		get_num(s);
	}
	void print(){
		if(num[0])
			putchar('-');
		bool leading_zero=1;
		for(int i=len;i;i--){
			if(leading_zero)
				printf("%d",num[i]);
			else
				printf("%02d",num[i]);
			leading_zero=0;
		}
		putchar('\n');
		return;
	}
};
const int N=1<<10,M=100;
int n,m;
bigint<114514> a,b,c;
int main(){
	a.read();
	b.read();
	c=a+b;
	c.print();
	return 0;
}
```

---

## 第四章 · 搜索篇

### 二分查找 · 偷看答案的演技

**二分哥**写了一个二分查找。

在 `[-1e9, 1e9]` 里猜一个数，猜 31 次。

每一次循环都做一次比较：`if(mid == a+b)`。

**他明明已经算了 a+b，却假装不知道。**

> "你考试时偷看了答案，然后假装自己算出来的。"

```cpp
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int a,b;
int s(int a,int b) {
    int l=-1e9,r=1e9,mid;
    while(l<r) {
        mid=(l+r)/2;
        if(mid==a+b) return mid;
        else if(mid>a+b) r=mid;
        else l=mid;
    }
}
int main() {
    cin>>a>>b;
    cout<<s(a,b);
    return 0;
}
```

---

### 模拟退火 · 物理模拟的误会

**模拟退火哥**把初始温度设为 100 万，降温系数 0.999，跑了 100 轮。

每轮 10 万次迭代，总共 1000 万次随机。

温度从 100 万降到 1e-10，终于收敛到了 3。

隔壁做物理模拟的过来围观："兄弟你在模拟什么？"

**"我在算 1+2。"**

他走了。

> "物理系同学：我们模拟分子运动，你们模拟什么？算加法。"

```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double d=0.999;
const double lim=1e-10;
ll a,b;
ll ans;
ll num;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int calc(int x)
{
    return abs(a+b-x)-abs(a+b-ans);
}
void ghost_fire()
{
    double T=1000000;
    while(T>lim)
    {
        int x=num+((rand()<<1)-RAND_MAX)*T;
        int del=calc(x);
        if(del<0)
        {
            ans=x;
            num=x;
        }
        else if(exp(-del/T)>(double)rand()/RAND_MAX) num=x;
        T*=d;
    }
}
void work()
{
    for(int i=1;i<=100;i++) ghost_fire();
}
int main()
{
    a=read();
    b=read();
    work();
    cout<<ans<<endl;
    return 0;
}
```

---

## 第五章 · 底层篇

### 虚拟机 · 为了一杯牛奶养了一头牛

**虚拟机哥**定义了一套 5 条指令的 ISA：LOAD、ADD、STORE、PRINT、HALT。

然后写了一个 100 行的解释器。

然后写了 6 条汇编指令。

然后在虚拟机上运行。

**然后得到了 3。**

> "为了算 1+2，我设计了一台计算机，定义了指令集，写了汇编程序，跑在虚拟机上……别人问为什么不用计算器？因为我的虚拟机没有计算器功能。"

```cpp
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <vector>
enum class OpCode { LOAD, ADD, STORE, PRINT, HALT };
struct Instruction { OpCode op; int operand1; int operand2; };
class VirtualMachine {
    std::vector<int> memory;
    std::vector<int> registers;
    size_t pc;
    bool running;
public:
    VirtualMachine(size_t memSize, size_t regCount)
        : memory(memSize, 0), registers(regCount, 0), pc(0), running(false) {}
    void execute(const std::vector<Instruction>& program) {
        running = true;
        while (running && pc < program.size()) {
            const auto& instr = program[pc];
            switch (instr.op) {
                case OpCode::LOAD: registers[instr.operand1] =
                instr.operand2; pc++; break;
                case OpCode::ADD: registers[instr.operand1] +=
                registers[instr.operand2]; pc++; break;
                case OpCode::STORE: memory[instr.operand1] =
                 registers[instr.operand2]; pc++; break;
                case OpCode::PRINT:
                std::cout << memory[instr.operand1] << std::endl;
                pc++; break;
                case OpCode::HALT: running = false; break;
                default: throw std::runtime_error("Unknown opcode");
            }
        }
    }
};
int main() {
    try {
        int a, b;
        std::cin >> a >> b;
        VirtualMachine vm(16, 4);
        std::vector<Instruction> program = {
            {OpCode::LOAD, 0, a},
            {OpCode::LOAD, 1, b},
            {OpCode::ADD, 0, 1},
            {OpCode::STORE, 0, 0},
            {OpCode::PRINT, 0, 0},
            {OpCode::HALT, 0, 0}
        };
        vm.execute(program);
        return 0;
    } catch (const std::exception& e) { return 1; }
}
```

---

## 第六章 · 语言篇

### 中文宏 · 编译器的翻译

**中文宏哥**用 `#define` 把 C++ 变成了中文：

编译器把中文翻译回英文，然后悄悄编译通过。

> "编译器：我翻译了一下，你就以为自己写的是中文编程了？"

```cpp
#include <bits/stdc++.h>
using namespace std;
#define 开始啦 main()
#define 开头 {
#define 结尾 }
#define 和 ,
#define 没了 return 0
#define 整数32位 int
#define 输入 cin
#define 输出 cout
#define 一个 >>
#define 这个 <<
#define 加上 +
#define 换行 '\n'
整数32位 开始啦
开头
    整数32位 a 和 b;
    输入 一个 a 一个 b;
    输出 这个 a 加上 b 这个 换行;
    没了;
结尾
```

---

### 文言文 · 三脸懵逼

**文言文哥**用 `wenyan-lang` 写了 A+B：

历史老师以为他在写《史记》，语文老师以为他在写古诗，编译器说：

**"我只能翻译成 JavaScript。"**

> "三脸懵逼：历史、语文、编译器。"

```
施「require('fs').readFileSync」於「「/dev/stdin」」。名之曰「數據」。
施「(buf => buf.toString().trim())」於「數據」。昔之「數據」者。今其是矣。
施「(s => s.split(' '))」於「數據」。昔之「數據」者。今其是矣。
注曰。「「文言尚菜，無對象之操作，故需 JavaScript 之语法」」。
夫「數據」之一。取一以施「parseInt」。名之曰「甲」。
夫「數據」之二。取一以施「parseInt」。名之曰「乙」。
加「甲」以「乙」。書之。
```

---

## 终章 · 群星闪耀时

这些人，有的写了 200 行，有的写了 1000 万次迭代，有的定义了一台虚拟机。

他们本可以写一行简单的加法，但他们没有。

**他们把简单的问题复杂化，把复杂的代码优雅化，把优雅的算法浪漫化。**

**他们不是在算 A+B。**

**他们是在向世界证明：**

> 程序员的浪漫，就是把一道入门题，写成一部史诗。

---

## 宇宙全家福

| 流派     | 代表作           | 全体致敬                             |
| -------- | ---------------- | ------------------------------------ |
| LCT      | 动态树算加法     | 相识->分手->复合，比偶像剧还曲折     |
| 线段树   | 标记永久化       | 用集装箱存一颗芝麻                   |
| 树状数组 | 50万空间存1个数  | 储物柜空着499999格                   |
| Splay    | 序列翻转         | 翻转证明交换律，数学老师哭了         |
| Treap    | 插200万个1       | CPU风扇转得比你脑子快                |
| Dijkstra | 三条边跑最短路   | 导航软件：我这就下岗？               |
| Kruskal  | INF边强行加戏    | 边：我不要面子的吗？                 |
| 完全平方 | 高精度开根       | 数学老师：公式不是这么用的           |
| FFT      | 高精度卷积算加法 | 蝴蝶还没来得及扇翅膀，加法已经算完了 |
| 二分查找 | 猜答案           | 偷看答案假装自己算的                 |
| 模拟退火 | 1000万次随机     | 物理系同学：你在模拟啥？算1+2        |
| 虚拟机   | 手搓ISA          | 为了喝牛奶养了一头牛                 |
| 中文宏   | #define 中文     | 编译器：我翻译了一下                 |
| 文言文   | 史记风代码       | 历史/语文/编译器三脸懵逼             |

---

## 后记

某日，一位萌新点开 A+B 的题解区。

他看到了 LCT、Splay、模拟退火、虚拟机、文言文……

他沉默了。

然后他写下了人生中第一段代码：

```cpp
#include<iostream>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}
```

他在那一刻突然明白：

> 所有的群星，都是在为最简单的真理闪烁。

> 而最简单的真理，往往只需要一行代码。

---

**THE END**