洛谷 P1601 A+B Problem（高精）

// ✗ 第 ① 版：所有人真实的第一反应 —— 一个 64 位整数读进来直接加
//
// 它不是瞎写：题面的数据范围**自己把它的分数写出来了**。
//
//   · 20% 的数据 a, b ≤ 10⁹  ⇒ 和 ≤ 2×10⁹，**连 int 都恰好装得下**（上限 2147483647，余量 7.4%）
//   · 40% 的数据 a, b ≤ 10¹⁸ ⇒ 和 ≤ 2×10¹⁸ < 9.22×10¹⁸ ⇒ **long long 稳稳的**
//   · 100% 的数据 a, b ≤ 10⁵⁰⁰ ⇒ 501 位，而 64 位整数只有 19~20 位 ⇒ **差 25 倍位数**
//
// ⇒ 这一版**稳拿 40 分**，而且是出题人明码标价递给你的 40 分。
//
// ⚠ 两处写法上的说明，都是为了让「它错成什么样」可复现：
//   ① 用 unsigned long long 而不是 long long —— **有符号溢出是 UB**，
//      演示一个错误写法的时候不能让它的输出依赖编译器（[第 45 章](/ch/45-estimate/)那条）；
//   ② `cin >> x` 读一个 501 位的数会**读失败**：C++11 起它把 x 置成该类型的最大值并设 failbit
//      （不是随机值，也不崩溃）⇒ **「它没崩」离「它对了」还差很远。**

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long a = 0, b = 0;
    cin >> a >> b;
    cout << a + b << "\n";          // unsigned 的溢出是「模 2⁶⁴ 绕回」，有定义
    return 0;
}

// P1601 A+B Problem（高精）—— ★ 正解：倒着存的十进制数组，一次加法
//
// 这一份就是[第 44 章第 7 步](/ch/44-bignum/)那个 add() 原样搬过来，
// 只是把「同时输出加减乘」换成了这道题要的那一行。
//
// 表示约定（和本章正文一字不差）：
//   · vector<int>，一格一位十进制数字，**下标 0 是个位**；
//   · 允许中途出现前导零（数组末尾的 0），最后统一由 trim() 去掉；
//   · **0 就是 {0}**，长度 1 —— trim() 里 `size() > 1` 那个 1 的全部理由。
//
// ⚠ 这道题的两个坑都不在算法里：
//   ① 题面写的是 `0 ≤ a, b` —— **0 是合法输入**，而 `0 + 0` 要打出一个 `0`，不是空行；
//   ② 循环条件里那个 `|| carry` ——「最高位再进一位」（999 + 1 = 1000）少了它就少一位。
//
// 复杂度 O(n)，n ≤ 501 ⇒ 什么都不用担心。

#include <bits/stdc++.h>
using namespace std;

using Big = vector<int>;

Big parse(const string& s) {
    Big v;
    for (int i = (int)s.size() - 1; i >= 0; i--) v.push_back(s[i] - '0');
    return v;
}

string show(const Big& v) {
    string s;
    for (int i = (int)v.size() - 1; i >= 0; i--) s += char('0' + v[i]);
    return s;
}

/** ★ 条件是 size() > 1，不是 !empty()：差一个字，0 就被删成空数组 */
void trim(Big& v) {
    while (v.size() > 1 && v.back() == 0) v.pop_back();
}

Big add(const Big& a, const Big& b) {
    Big c;
    int carry = 0;
    // ★ `|| carry` 就是「最高位还要再进一位」那一格
    for (size_t i = 0; i < a.size() || i < b.size() || carry; i++) {
        int cur = carry;
        if (i < a.size()) cur += a[i];
        if (i < b.size()) cur += b[i];
        c.push_back(cur % 10);
        carry = cur / 10;
    }
    trim(c);
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string sa, sb;
    if (!(cin >> sa >> sb)) return 0;
    cout << show(add(parse(sa), parse(sb))) << "\n";
    return 0;
}

// P1601 解析页上所有数字的出处。./p1601Count [csv]
//
// 四件事：
//   ① 题面那三档数据范围各自意味着什么（20% 档连 int 都恰好够，余量算出来）；
//   ② 四个档位里每个 bug 的**触发条件**各满足了多少轮（用来和对拍的抓获数逐格对）；
//   ③ 「a + b 的位数只可能是 max(la, lb) 或者它 + 1」—— 小范围全枚举，0 组例外；
//   ④ 顶格一次加法要做多少次一位数加法。
#include <bits/stdc++.h>
using namespace std;

/** 高位在前的字符串加法（只在这份统计程序里用，和被测的几版都不共享代码） */
static string addStr(const string& x, const string& y) {
    size_t n = max(x.size(), y.size());
    string a = string(n - x.size(), '0') + x, b = string(n - y.size(), '0') + y, c(n, '0');
    int carry = 0;
    for (size_t k = n; k-- > 0;) {
        int cur = (a[k] - '0') + (b[k] - '0') + carry;
        c[k] = char('0' + cur % 10);
        carry = cur / 10;
    }
    if (carry) c = char('0' + carry) + c;
    size_t i = 0;
    while (i + 1 < c.size() && c[i] == '0') i++;
    return c.substr(i);
}

/** 和 p1601Gen.cpp 一模一样的一份，用来数「触发条件满足了多少轮」 */
static void gen(unsigned seed, int mode, string& a, string& b) {
    mt19937 rng(seed * 1000003u + 20260904u);
    int lo = mode == 3 ? 495 : 1, hi = mode == 3 ? 501 : 12;
    unsigned r1 = rng() % (unsigned)(hi - lo + 1);
    unsigned r2 = rng() % (unsigned)(hi - lo + 1);
    int la = lo + (int)r1, lb = lo + (int)r2;
    if (mode == 1) lb = la;
    auto one = [&](int len) {
        string s;
        unsigned h = rng() % 9u;
        s += char('1' + h);
        for (int i = 1; i < len; i++) { unsigned d = rng() % 10u; s += char('0' + d); }
        return s;
    };
    a = one(la); b = one(lb);
    if (mode == 2) {
        unsigned z1 = rng() % 2u, z2 = rng() % 2u;
        if (z1) a = "0";
        if (z2) b = "0";
    }
}

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";

    // ① 题面那三档
    const long long INT_MAXV = 2147483647LL;
    long long sum20 = 2000000000LL;                       // 20% 档：a, b ≤ 10⁹ ⇒ 和 ≤ 2×10⁹
    double intMargin = 100.0 * (double)(INT_MAXV - sum20) / (double)sum20;
    unsigned long long llMax = 9223372036854775807ULL;
    double llRatio = (double)llMax / 2e18;                // 40% 档：和 ≤ 2×10¹⁸

    // ③ 位数上界：小范围全枚举
    int bad = 0, hitPlus1 = 0, total = 0;
    for (int a = 0; a <= 999; a++)
        for (int b = 0; b <= 999; b++) {
            string sa = to_string(a), sb = to_string(b), sc = addStr(sa, sb);
            size_t mx = max(sa.size(), sb.size());
            total++;
            if (sc.size() != mx && sc.size() != mx + 1) bad++;
            if (sc.size() == mx + 1) hitPlus1++;
        }

    // ② 四个档位的触发计数
    int tAlign[4] = {0, 0, 0, 0}, tCarry[4] = {0, 0, 0, 0}, tTrim[4] = {0, 0, 0, 0}, tLl[4] = {0, 0, 0, 0};
    for (int mode = 0; mode < 4; mode++)
        for (unsigned s = 1; s <= 300; s++) {
            string a, b;
            gen(s, mode, a, b);
            string c = addStr(a, b);
            size_t mx = max(a.size(), b.size());
            // ★ 左对齐会错的条件是**两层**：位数不同 **而且**短的那个不是 0
            //   （短的是 0 时，左对齐只是把 0 挪到了高位，加上去还是 0 ⇒ 它照样对）
            if (a.size() != b.size() && a != "0" && b != "0") tAlign[mode]++;
            if (c.size() > mx) tCarry[mode]++;                         // 最高位真的进了一位
            if (a == "0" && b == "0") tTrim[mode]++;                   // 答案是 0
            if (a.size() > 20 || b.size() > 20) tLl[mode]++;            // 64 位整数读不进来
        }

    long long topOps = 501 + 1;                                        // 顶格：最多 502 次一位数加法

    if (csv) {
        printf("intMargin,%.2f\n", intMargin);
        printf("llRatio,%.2f\n", llRatio);
        printf("lenCases,%d\n", total);
        printf("lenBad,%d\n", bad);
        printf("lenPlus1,%d\n", hitPlus1);
        printf("topOps,%lld\n", topOps);
        for (int m = 0; m < 4; m++) printf("trigAlign%d,%d\n", m, tAlign[m]);
        for (int m = 0; m < 4; m++) printf("trigCarry%d,%d\n", m, tCarry[m]);
        for (int m = 0; m < 4; m++) printf("trigTrim%d,%d\n", m, tTrim[m]);
        for (int m = 0; m < 4; m++) printf("trigLl%d,%d\n", m, tLl[m]);
        return 0;
    }

    printf("=== 题面那三档数据范围，各自是什么意思 ===\n");
    printf("20%% 档 a, b <= 1e9  => 和 <= %lld，int 上限 %lld，**恰好够**，余量只有 %.2f%%\n",
           sum20, INT_MAXV, intMargin);
    printf("40%% 档 a, b <= 1e18 => 和 <= 2e18，long long 上限 %llu，余量 %.2f 倍\n", llMax, llRatio);
    printf("100%% 档 a, b <= 1e500 => 501 位，64 位整数只有 19~20 位\n\n");

    printf("=== 位数上界：len(a+b) 只可能是 max(la,lb) 或者它 + 1 ===\n");
    printf("全枚举 a, b <= 999 共 %d 组：例外 %d 组；其中真的多出一位的 %d 组\n\n", total, bad, hitPlus1);

    printf("=== 四个档位 × 每个 bug 的触发条件（各 300 轮）===\n");
    printf("%-34s %6s %6s %6s %6s\n", "触发条件", "档0", "档1", "档2", "档3");
    printf("%-34s %6d %6d %6d %6d\n", "位数不同且都不是 0（左对齐会错）", tAlign[0], tAlign[1], tAlign[2], tAlign[3]);
    printf("%-34s %6d %6d %6d %6d\n", "最高位真的进了一位（|| carry）", tCarry[0], tCarry[1], tCarry[2], tCarry[3]);
    printf("%-34s %6d %6d %6d %6d\n", "答案是 0（trim 删过头）", tTrim[0], tTrim[1], tTrim[2], tTrim[3]);
    printf("%-34s %6d %6d %6d %6d\n", "有数超过 20 位（64 位读不进）", tLl[0], tLl[1], tLl[2], tLl[3]);
    printf("\n顶格一次加法：最多 %lld 次一位数加法 —— 时限 1 秒，量级差得太远，秒表在这一章没用\n", topOps);
    return 0;
}