洛谷 P1009 [NOIP 1998 普及组] 阶乘之和

// ✗ 第 ① 版：64 位整数累加 —— 这就是题面点名的「书里那份过不了的代码」
//
// 题面的【其他说明】里写着：
//   「《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 n ≤ 20，
//     使用书中的代码无法通过本题。」
//
// ⇒ ★★ 这是本书见过的**最直白的一次**：出题人不但告诉你暴力会挂，
//   还告诉你它挂在哪儿。而那条线是能精确算出来的：
//
//        n = 20：S = 2561327494111820313  ——  19 位，long long（上限 9.22×10¹⁸）**装得下**
//        n = 21：21! 就已经是 5.1×10¹⁹    ——  **第一个装不下的**
//
//   ⇒ 这一版在 n ≤ 20 上**逐字节正确**，n ≥ 21 起全错。而题面的 n 可以到 50。
//
// ⚠ 用 unsigned long long 是为了让它错得可复现（有符号溢出是 UB）；
//   unsigned 的溢出是「模 2⁶⁴ 绕回」，有定义 —— 所以它会安静地打出一个错的数，不会崩。

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

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

    int n = 0;
    if (!(cin >> n)) return 0;

    unsigned long long cur = 1, sum = 0;
    for (int i = 1; i <= n; i++) { cur *= (unsigned long long)i; sum += cur; }
    cout << sum << "\n";
    return 0;
}

// P1009 [NOIP 1998 普及组] 阶乘之和 —— ★ 正解：高精度加法 ＋ 高精度乘低精度
//
// ★★ 这道题是「什么时候必须上高精度」最经典的一个例子，而且**题面自己把理由写出来了**：
//   「注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 n ≤ 20，
//     使用书中的代码无法通过本题。」
//   —— 书里那份代码就是 p1009Ll.cpp（64 位整数累加），而那条线**精确在 n = 21**。
//
// 算法只有三行，一个循环就够（**不用每次重算阶乘**）：
//
//        cur = 1                       // cur 始终是 i!
//        for i = 1..n:  cur *= i       // 高精度 × 低精度（i ≤ 50，一个 int 就够）
//                       sum += cur     // 高精度 + 高精度
//
// ★ 「高精乘低精」和第 8 步那个「高精乘高精」不是一回事，它便宜得多：
//   一遍扫过去，每一位乘上 k 再进位 —— O(len)，而不是 O(len × len)。
//   ⚠ 而它的进位**可以大于 9**：一位最多 9×50 + 上一次的进位 ⇒ 进位能到 40 多。
//     所以收尾那句必须是 `while (carry) { push(carry % 10); carry /= 10; }`，
//     写成「if (carry) 补一位」就会丢位（p1009Tail.cpp 就是它）。
//
// 顶格 n = 50：50! 有 65 位，答案 S 也是 65 位（★ 50 个 n 里两者位数**从没不同过**）
// —— 一共只有 **1355** 次一位数乘法。

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

using Big = vector<int>;                       // 下标 0 是个位

static void trim(Big& v) { while (v.size() > 1 && v.back() == 0) v.pop_back(); }

/** 高精度 × 低精度：一遍扫过去，进位带着走 */
static Big mulSmall(const Big& a, int k) {
    Big c;
    int carry = 0;
    for (size_t i = 0; i < a.size(); i++) {
        int cur = a[i] * k + carry;
        c.push_back(cur % 10);
        carry = cur / 10;
    }
    while (carry) { c.push_back(carry % 10); carry /= 10; }   // ★ 是 while，不是 if
    trim(c);
    return c;
}

static Big add(const Big& a, const Big& b) {
    Big c;
    int carry = 0;
    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);

    int n = 0;
    if (!(cin >> n)) return 0;

    Big cur{1}, sum{0};
    for (int i = 1; i <= n; i++) {
        cur = mulSmall(cur, i);                 // cur = i!
        sum = add(sum, cur);
    }

    string s;
    for (int i = (int)sum.size() - 1; i >= 0; i--) s += char('0' + sum[i]);
    cout << s << "\n";
    return 0;
}

// P1009 解析页上所有数字的出处。./p1009Count [csv]
//
// ★★★ 这道题最值钱的一句话是**方法论**，不是算法：
//   **它的输入空间只有 50 个整数** —— `1 ≤ n ≤ 50`。
//   ⇒ 用不着写生成器、用不着对拍：**把 50 个 n 全跑一遍**，
//     每个版本从哪个 n 开始错、错在哪一位，全是精确值，不是抓获率。
//   ⇒ [「输入空间小的时候，算一遍比对拍又快又充分」](/sol/p1002/)的又一次
//     —— 而这一次连「小」都不用打折：50 个。
//
// 这份程序里每个版本都独立重写了一遍，输出四件事：
//   ① 每个错法**第一个出错的 n**（精确到一个整数）；
//   ② 用 __int128 走一条完全无关的路：n ≤ 33 上和硬件算术逐个核对；
//   ③ n! 和 S(n) 的位数表（顶格 50! 有多少位）；
//   ④ 正解 vs「每次从头重算阶乘」的一位数乘法次数。
#include <bits/stdc++.h>
using namespace std;

using Big = vector<int>;
static void trim(Big& v) { while (v.size() > 1 && v.back() == 0) v.pop_back(); }
static string show(const Big& v) {
    string s;
    for (int i = (int)v.size() - 1; i >= 0; i--) s += char('0' + v[i]);
    return s;
}
static Big add(const Big& a, const Big& b) {
    Big c; int carry = 0;
    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;
}
/** 正解的乘低精；ops 累加一位数乘法的次数 */
static Big mulOk(const Big& a, int k, long long* ops) {
    Big c; int carry = 0;
    for (size_t i = 0; i < a.size(); i++) {
        if (ops) (*ops)++;
        int cur = a[i] * k + carry;
        c.push_back(cur % 10); carry = cur / 10;
    }
    while (carry) { c.push_back(carry % 10); carry /= 10; }
    trim(c); return c;
}
/** ✗ 只补一位 carry */
static Big mulTail(const Big& a, int k) {
    Big c; int carry = 0;
    for (size_t i = 0; i < a.size(); i++) {
        int cur = a[i] * k + carry;
        c.push_back(cur % 10); carry = cur / 10;
    }
    if (carry) c.push_back(carry % 10);
    trim(c); return c;
}
/** ✗ 先写回这一位再拿它算进位 */
static Big mulCarry(const Big& a, int k) {
    Big c(a.size(), 0); int carry = 0;
    for (size_t i = 0; i < a.size(); i++) {
        c[i] = (a[i] * k + carry) % 10;
        carry = (c[i] * k + carry) / 10;
    }
    while (carry) { c.push_back(carry % 10); carry /= 10; }
    trim(c); return c;
}
static string i128ToStr(__int128 v) {
    if (v == 0) return "0";
    string s;
    while (v > 0) { s += char('0' + (int)(v % 10)); v /= 10; }
    reverse(s.begin(), s.end());
    return s;
}

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

    int firstLl = 0, firstTail = 0, firstCarry = 0, refacBad = 0;
    int i128Cases = 0, i128Bad = 0, maxCarry = 0, firstBigCarry = 0;
    int lenFact50 = 0, lenSum50 = 0, lenDiff = 0;
    long long opsOk = 0, opsRefac = 0;

    Big cur{1}, sum{0};
    unsigned long long lcur = 1, lsum = 0;
    Big tcur{1}, tsum{0};                 // Tail 版
    Big ccur{1}, csum{0};                 // Carry 版
    __int128 icur = 1, isum = 0;

    for (int n = 1; n <= 50; n++) {
        // 正解
        cur = mulOk(cur, n, &opsOk);
        sum = add(sum, cur);
        string want = show(sum);

        // ✗ 64 位
        lcur *= (unsigned long long)n; lsum += lcur;
        if (!firstLl && to_string(lsum) != want) firstLl = n;

        // ✗ 只补一位
        tcur = mulTail(tcur, n); tsum = add(tsum, tcur);
        if (!firstTail && show(tsum) != want) firstTail = n;

        // ✗ 先写回再算进位
        ccur = mulCarry(ccur, n); csum = add(csum, ccur);
        if (!firstCarry && show(csum) != want) firstCarry = n;

        // 「每次从头重算」—— 答案应该永远一样
        {
            Big s2{0};
            for (int i = 1; i <= n; i++) {
                Big c2{1};
                for (int j = 1; j <= i; j++) c2 = mulOk(c2, j, n == 50 ? &opsRefac : nullptr);
                s2 = add(s2, c2);
            }
            if (show(s2) != want) refacBad++;
        }

        // ② 完全无关的一条路：__int128（n ≤ 33 之内它装得下）
        if (n <= 33) {
            icur *= (__int128)n; isum += icur;
            i128Cases++;
            if (i128ToStr(isum) != want) i128Bad++;
        }

        // 「乘低精的收尾进位」到底能有多大 —— Tail 那个 bug 的触发条件
        {
            int carry = 0;
            Big f = cur;                       // 这一步之后 cur 就是 n!
            // 重算一次 (n-1)! * n 的收尾进位
            Big prev{1};
            for (int i = 1; i < n; i++) prev = mulOk(prev, i, nullptr);
            carry = 0;
            for (size_t i = 0; i < prev.size(); i++) { int c2 = prev[i] * n + carry; carry = c2 / 10; }
            if (carry > maxCarry) maxCarry = carry;
            if (!firstBigCarry && carry >= 10) firstBigCarry = n;
            (void)f;
        }

        if (n == 50) {
            lenFact50 = (int)cur.size();
            lenSum50 = (int)sum.size();
        }
        if (cur.size() != sum.size()) lenDiff++;
    }

    if (csv) {
        printf("firstLl,%d\n", firstLl);
        printf("firstTail,%d\n", firstTail);
        printf("firstCarry,%d\n", firstCarry);
        printf("refacBad,%d\n", refacBad);
        printf("i128Cases,%d\n", i128Cases);
        printf("i128Bad,%d\n", i128Bad);
        printf("maxCarry,%d\n", maxCarry);
        printf("firstBigCarry,%d\n", firstBigCarry);
        printf("lenFact50,%d\n", lenFact50);
        printf("lenSum50,%d\n", lenSum50);
        printf("lenDiff,%d\n", lenDiff);
        printf("opsOk,%lld\n", opsOk);
        printf("opsRefac,%lld\n", opsRefac);
        printf("opsRatio,%.1f\n", (double)opsRefac / (double)opsOk);
        printf("sum50,%s\n", show(sum).c_str());
        return 0;
    }

    printf("=== 输入空间只有 50 个整数 ⇒ 不写生成器，全跑一遍 ===\n");
    printf("✗ 64 位整数累加      第一个出错的 n = %d   （书里那份代码的数据范围正好是 n <= 20）\n", firstLl);
    printf("✗ 乘低精只补一位进位 第一个出错的 n = %d   （收尾进位第一次 >= 10 是在 n = %d，最大 %d）\n",
           firstTail, firstBigCarry, maxCarry);
    printf("✗ 先写回再算进位     第一个出错的 n = %d\n", firstCarry);
    printf("★ 每次从头重算阶乘   50 个 n 里出错 %d 个（它是对的，只是多做了活）\n\n", refacBad);

    printf("=== 换一把尺子：__int128 走一条完全无关的路 ===\n");
    printf("n <= 33 上硬件算术能装下 ⇒ %d 组逐字节核对，对不上 %d 组\n\n", i128Cases, i128Bad);

    printf("=== 位数 ===\n");
    printf("50! 有 %d 位；S(50) 有 %d 位；50 个 n 里两者位数不同的有 %d 个\n", lenFact50, lenSum50, lenDiff);
    printf("S(50) = %s\n\n", show(sum).c_str());

    printf("=== 一位数乘法次数（n = 50）===\n");
    printf("正解（cur 滚着乘）    %lld 次\n", opsOk);
    printf("每次从头重算阶乘      %lld 次   ⇒ 多 %.1f 倍\n", opsRefac, (double)opsRefac / (double)opsOk);
    printf("⚠ 两版都是零点几毫秒 —— 秒表在这一章量不动，只能数次数\n");
    return 0;
}