洛谷 P1255 数楼梯

// 洛谷 P1255 数楼梯 —— 第 ① 版：照题意直接写递归（对，但跑不完）
//
// 输入：N（1 <= N <= 5000）
// 输出：走法总数
//
// 这份为什么存在：题意翻译成递归只有一行 ——
// 最后一步要么迈一阶、要么迈两阶，所以 f(n) = f(n-1) + f(n-2)。
// 这就是斐波那契，也是第 1 章正文里那个「同一个子问题被算了无数遍」的活标本。
//
// ⚠ 慢到什么程度：**调用次数正好是 2 * f(n-1) - 1**（p1255Count.cpp 逐行比给你看）。
//    ⚠ 这个式子是**跑出来才对上的**：一开始猜的是 2 * f(n) - 1，一比就差了一整阶。
//      「看着显然」的式子也要跑一遍 —— 这本书踩过好几次。
//    总之调用次数和答案是同一个量级：f(45) 已经十亿，而题目要的是 f(5000) —— 那个数有 1045 位。
//    ⇒ 它不是「慢一点」，是**这辈子都跑不完**。
//
// ★ 第 1 章那句「先别急着优化，记住这个感觉」说的就是它。
//   下一版加一个数组就好了；再下一版才轮到这道题真正的难点：数太大，long long 装不下。

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

long long f(int n) {
    if (n == 1) return 1;                              // 一阶：只有一种走法
    if (n == 2) return 2;                              // 两阶：1+1 或 2
    return f(n - 1) + f(n - 2);
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    cout << f(n) << "\n";
    return 0;
}

// 洛谷 P1255 数楼梯 —— 第 ② 版：改成递推，快得飞起（**但答案是错的**）
//
// 输入：N
// 输出：走法总数
//
// 这份为什么存在：把递归倒过来从小往大推，一个循环就完事，
// **快的问题当场解决**（5000 阶眨眼就跑完）。很多人写到这儿就交了。
//
// ⚠ 一处刻意的写法：这里用的是 **unsigned long long**，不是 long long。
//   真实的错误当然是用 long long 写的，但**有符号溢出在 C++ 里是未定义行为** ——
//   换个编译器、换个优化档，它吐出来的数就可能不一样，那样这一页就没法拿数字说话了。
//   unsigned 的溢出**有明确定义**（对 2^64 取模），于是「错的那个数」也是可复现的。
//   ⇒ 演示「这样写是错的」时，要让那个错本身是确定的。（第 44 章立的规矩。）
//
// ⚠⚠ 然后就 WA 了，而且**样例是过的** —— 这是这道题最坑人的地方。
//    N = 4 输出 5，N = 40 也对，到第 92 阶（无符号）/ 第 91 阶（有符号）为止都还对，
//    再往后它会给出一个**看起来很正常、其实完全错误的数**（溢出之后无声无息）。
//    题目要的是 N = 5000，那个答案有 **1045 位**。
//
// ★ 记住这条：**「跑得动」和「答案对」是两回事，而溢出属于后者。**
//   对拍也救不了你 —— 两份都用 long long 的话，它们会一起错，而且错得一模一样。
//   ⇒ 唯一的办法是**动手前先估一估答案能有多大**（第 44 章整章在讲这件事）。
//
// p1255Count.cpp 会把「从第几阶开始溢出」精确地找出来。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<unsigned long long> f(max(n, 2) + 1);
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];

    cout << f[n] << "\n";
    return 0;
}

// 洛谷 P1255 数楼梯 —— 第 ③ 版：递推 + 高精度加法（正解）
//
// 输入：N（1 <= N <= 5000）
// 输出：走法总数（N = 5000 时是一个 1045 位的数）
//
// 和第 ② 版的差别只有一处：**把 long long 换成「一个数组存一个大数」**。
// 递推那两行的形状一模一样，还是 f[i] = f[i-1] + f[i-2]。
//
// 高精度加法就是竖式加法，小学怎么算的就怎么写：
//   · 每一位存一个十进制数字，**低位在前**（下标 0 是个位）—— 这样进位是「往后加」，不用挪数组
//   · 逐位相加，超过 10 就往上一位进 1
//
// ⚠ 低位在前是约定，不是随便挑的：加法、乘法都是从低位往高位算，
//   存成「低位在前」之后下标和数位就一一对应了，最后输出时倒着打一遍即可。
//   （第 44 章整章讲这件事，这里只用得上最简单的加法。）

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

/** 大数：低位在前，每个元素是一个十进制数字 */
using Big = vector<int>;

Big fromInt(int x) {
    Big a;
    if (x == 0) a.push_back(0);
    while (x > 0) { a.push_back(x % 10); x /= 10; }
    return a;
}

/** 竖式加法：逐位相加，满十进一 */
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 s = carry;
        if (i < a.size()) s += a[i];
        if (i < b.size()) s += b[i];
        c.push_back(s % 10);
        carry = s / 10;
    }
    return c;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<Big> f(max(n, 2) + 1);
    f[1] = fromInt(1);
    f[2] = fromInt(2);
    for (int i = 3; i <= n; i++) f[i] = add(f[i - 1], f[i - 2]);

    const Big& ans = f[n];
    for (size_t i = ans.size(); i-- > 0; ) cout << ans[i];      // 低位在前，倒着输出
    cout << "\n";
    return 0;
}

// P1255 的三个版本各卡在哪 —— 两把可复现的尺子
//
// 输入：无
// 输出：两张表
//   表一：朴素递归的调用次数（并验证它恒等于 2 × f(n) − 1）
//   表二：long long 从第几阶开始装不下，以及答案有多少位
//
// ★ 这份代码要说明的是两件**性质不同**的失败：
//   · 第 ① 版失败在**时间**上 —— 调用次数是答案的两倍，而答案本身就大得没边；
//   · 第 ② 版失败在**数值**上 —— 它跑得飞快，只是从某一阶开始悄悄给出错的数。
//   前者你会看到 TLE，后者你只会看到 WA，而且样例还是过的。
//
// ⚠ 表二用 __int128 当裁判：它能装到 1.7 × 10^38，足够看清 long long 在哪一步开始跑偏。
//   （第 44 章 verify.cpp 用的是同一招：换一把更长的尺子去量原来那把。）

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

long long calls = 0;
long long fib(int n) {
    calls++;
    if (n == 1) return 1;
    if (n == 2) return 2;
    return fib(n - 1) + fib(n - 2);
}

/** 大数位数：只算位数，不算值 */
int digitsOf(int n) {
    vector<int> a{1}, b{2}, c;
    if (n == 1) return 1;
    if (n == 2) return 1;
    for (int i = 3; i <= n; i++) {
        c.clear();
        int carry = 0;
        for (size_t k = 0; k < a.size() || k < b.size() || carry; k++) {
            int s = carry;
            if (k < a.size()) s += a[k];
            if (k < b.size()) s += b[k];
            c.push_back(s % 10);
            carry = s / 10;
        }
        a = b;
        b = c;
    }
    return (int)b.size();
}

int main() {
    // 先把 f 递推出来（第 ③ 列要用 f[n-1]）
    vector<long long> f(45);
    f[1] = 1; f[2] = 2;
    for (int i = 3; i < 45; i++) f[i] = f[i - 1] + f[i - 2];

    cout << "表一：朴素递归要调用多少次\n\n";
    cout << "    n       答案 f(n)      调用次数    2*f(n-1)-1\n";
    cout << "-----   -------------   -----------   -----------\n";
    for (int n : {4, 10, 20, 30, 40}) {
        calls = 0;
        long long v = fib(n);
        cout << setw(5) << n
             << setw(16) << v
             << setw(14) << calls
             << setw(14) << 2 * f[n - 1] - 1 << "\n";
    }
    cout << "\n后两列永远相等：调用次数 = 2 * f(n-1) - 1。\n";
    cout << "也就是说它和答案是同一个量级 —— 所以「答案大」就等于「跑不完」，优化循环救不了。\n";
    cout << "⚠ 这个式子是跑出来才对上的：先猜的是 2*f(n)-1，一比就发现差了一整阶。\n";

    cout << "\n表二：64 位整数最多能撑到第几阶\n\n";
    // ⚠ 用 __int128 递推真值，再和两条上限比 —— 全程没有溢出，结论是确定的。
    //   （直接让 long long 溢出去看它变成什么，是**未定义行为**，不能拿来当证据。）
    const __int128 LL_MAX = (__int128)9223372036854775807LL;
    const __int128 ULL_MAX = ((__int128)1 << 64) - 1;
    __int128 A = 1, B = 2;                     // f(1), f(2)
    int lastLL = 2, lastULL = 2;
    // ⚠ 只推到第 100 阶就够了 —— 再往下推，连 __int128 自己都会溢出，
    //   那样这把「裁判尺」本身就不可信了。（量东西之前先确认尺子够长。）
    for (int i = 3; i <= 100; i++) {
        __int128 C = A + B;
        if (C <= LL_MAX) lastLL = i;
        if (C <= ULL_MAX) lastULL = i;
        A = B; B = C;
    }
    cout << "64 位有符号 (long long)      最多到第 " << lastLL << " 阶\n";
    cout << "64 位无符号 (unsigned)       最多到第 " << lastULL << " 阶\n";
    cout << "题目要的                     第 5000 阶，答案有 " << digitsOf(5000) << " 位\n";
    cout << "\n⇒ 差的不是「大一点」，是差着 " << digitsOf(5000) / 19 << " 个 long long 那么长。\n";
    return 0;
}