洛谷 P1044 栈

// 洛谷 P1044 栈 —— 第 ③ 版：换个角度想，它是卡特兰数
//
// 输入：n
// 输出：可能的输出序列总数
//
// 这份为什么存在：记忆化已经能过了。这一版不是为了更快（都是一瞬间），
// 是为了**看清这道题到底是什么**。
//
// 换个角度：盯住「**1 号数字是第几个被输出的**」。
// 假设 1 是第 k+1 个被输出的，那么在它之前必须先输出 k 个数 ——
// 而这 k 个数只能来自 2..k+1（因为 1 还压在栈底，比它晚进栈的才可能先出来）。
// 于是整个问题被切成两段互不干扰的小问题：
//
//   前面那段：k 个数自己排  ⇒ f(k)
//   后面那段：剩下 n-1-k 个数自己排 ⇒ f(n-1-k)
//
//   f(n) = f(0)·f(n-1) + f(1)·f(n-2) + ... + f(n-1)·f(0)      f(0) = 1
//
// 这就是**卡特兰数**（Catalan）。f(3) = 5，正好是样例。
//
// ★ 值得记住的不是「卡特兰数」这个名字，是那个动作：
//   **盯住某一个元素，按它的位置把问题劈成两半。** 第 26 章区间 DP 用的是同一招。
//
// ⚠ 但也别倒过来想：**先会写第 ② 版的记忆化，再去认公式。**
//   认不出公式的题多得是，而「状态 + 记忆化」永远能用。

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

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

    vector<long long> f(n + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int k = 0; k < i; k++) f[i] += f[k] * f[i - 1 - k];

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

// P1044 的两个递归版本各走多少个节点 —— 换一把可复现的尺子
//
// 输入：无（表是写死的几个 n；第 ① 列超过 n = 16 就跑不动了，所以表到 16 为止）
// 输出：一张表，对每个 n 列出
//         答案 f(n)        可能的输出序列总数
//         1.没有记忆化      走过的节点数
//         2.有记忆化        调用次数（含直接命中缓存的那些）
//         真正算过的格子     记忆化下有多少个 (rest, in) 被真的算了一遍
//
// ★ 最后一列是这道题的题眼：**它正好是 n(n+1)/2**，因为能走到的状态就是
//   rest 取 1..n、in 取 0..n-rest —— 数一数就这么多，和答案有多大毫无关系。
//   ⇒ 「该不该上记忆化」这个判断，看的就是它：状态的组合数够小，就一定划算。
//
// ⚠ 第 ① 列的增长和答案本身一个量级（都是卡特兰数那条曲线），
//   所以它和 P1255、P1028 是同一种慢：**工作量跟着答案一起爆炸**。

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

int n;
long long naiveNodes = 0;

long long naive(int rest, int in) {
    naiveNodes++;
    if (rest == 0) return 1;
    long long total = naive(rest - 1, in + 1);
    if (in > 0) total += naive(rest, in - 1);
    return total;
}

long long memo[25][25];
long long memoCalls = 0, memoFilled = 0;

long long withMemo(int rest, int in) {
    memoCalls++;
    if (rest == 0) return 1;
    if (memo[rest][in] >= 0) return memo[rest][in];
    memoFilled++;
    long long total = withMemo(rest - 1, in + 1);
    if (in > 0) total += withMemo(rest, in - 1);
    return memo[rest][in] = total;
}

int main() {
    cout << "    n       答案 f(n)      1.没记忆化    2.有记忆化  真正算的格子\n";
    cout << "-----   -------------   -------------   -----------   -----------\n";

    for (int k : {3, 5, 10, 13, 15, 16}) {
        n = k;
        naiveNodes = 0;
        long long ans = naive(k, 0);

        memset(memo, -1, sizeof memo);
        memoCalls = memoFilled = 0;
        withMemo(k, 0);

        cout << setw(5) << k
             << setw(16) << ans
             << setw(16) << naiveNodes
             << setw(14) << memoCalls
             << setw(14) << memoFilled << "\n";
    }

    cout << "\n最后一列正好是 n(n+1)/2（自己对一对：3->6, 5->15, 10->55, 16->136）——\n";
    cout << "因为能走到的状态就是 rest 取 1..n、in 取 0..n-rest，数一数就是这么多。\n";
    cout << "题目的上界 n = 18：第 1 列到那时是十亿量级，而最后一列只有 171 个格子。\n";
    return 0;
}

// ★ 第 ④ 版：闭形式 —— 卡特兰数 C(2n, n) / (n+1)
//
// [第 43 章](/ch/43-combinatorics/)给出的那条闭形式。第 ③ 版是**递推**
// （f(n) = Σ f(i)·f(n−1−i)，O(n²) 次乘法），这一版**一个循环、n 次乘法**就完了。
//
// ⚠ 但「有闭形式」不等于「照着公式抄」：
//   直接写 (2n)! / (n! · n! · (n+1)) 是**算不出来**的 —— 36! ≈ 3.7×10⁴¹，
//   long long 只能装到 20!（见 p1044Fact.cpp）。
//
// ★ 走得通的写法是**边乘边除**：
//     C(2n, n) = ∏(i = 1..n) (n + i) / i
//   而且**每一步除法都是整除** —— 因为前 i 步乘完除完之后正好是 C(n+i, i)，
//   它本身就是个整数。⇒ 全程不掉精度、不用高精度、不用逆元。
//
// ⚠ 题面 n ≤ 18 ⇒ **不用取模**，可以直接看清楚原始的样子
//   （而中间值 C(36,18) = 9 075 135 300 已经撑破 int 了，见 p1044Int.cpp）。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll n;
    if (scanf("%lld", &n) != 1) return 0;
    ll c = 1;
    for (ll i = 1; i <= n; i++) c = c * (n + i) / i;   // 每一步都恰好是 C(n+i, i)
    printf("%lld\n", c / (n + 1));
    return 0;
}

// P1044 第 ④ 版（闭形式）那一节的度量程序：./p1044Cat csv
//
//   line  : ★ 三种写法各自的**溢出线**在 n 的哪一格（照着题面 n ≤ 18 全枚举，一格不落）。
//   exact : ★★ 「边乘边除每一步都整除」不是运气 —— 把每一步的余数都验一遍。
//   alt   : ★★ 一条和除法完全无关的路：C(n) = C(2n,n) − C(2n,n+1)，逐个对一遍。
//   ops   : ★ 递推（O(n²)）和闭形式（O(n)）的乘法次数。
//
// ⚠ 这道题的输入空间只有 18 个值 ⇒ [「算一遍」比「对拍」又快又充分](/sol/p1002/)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int NMAX = 18;

/** 第 ③ 版：卡特兰递推 f(n) = Σ f(i)·f(n−1−i) */
static ll rec(int n, ll* opsOut) {
    ll f[NMAX + 1] = {0};
    ll ops = 0;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = 0;
        for (int j = 0; j < i; j++) { f[i] += f[j] * f[i - 1 - j]; ops++; }
    }
    if (opsOut) *opsOut = ops;
    return f[n];
}

/** 第 ④ 版：闭形式，边乘边除 */
static ll closed(int n, ll* opsOut, ll* maxMid, bool* allExact) {
    ll c = 1, ops = 0, mx = 1;
    bool exact = true;
    for (int i = 1; i <= n; i++) {
        ll t = c * (n + i);
        if (t > mx) mx = t;
        if (t % i != 0) exact = false;          // ★ 这一步除得尽吗
        c = t / i;
        if (c > mx) mx = c;
        ops++;
    }
    if (opsOut) *opsOut = ops;
    if (maxMid) *maxMid = mx;
    if (allExact) *allExact = exact;
    return c / (n + 1);
}

/** ✗ 三个阶乘各算一遍 */
static ll byFact(int n) {
    ll f2n = 1, fn = 1;
    for (ll i = 1; i <= 2 * n; i++) f2n *= i;
    for (ll i = 1; i <= n; i++) fn *= i;
    return f2n / (fn * fn) / (n + 1);
}

/** ✗ 边乘边除但用 32 位（unsigned，绕回是明确定义的） */
static unsigned byInt(int n) {
    unsigned c = 1;
    for (unsigned i = 1; i <= (unsigned)n; i++) c = c * ((unsigned)n + i) / i;
    return c / ((unsigned)n + 1);
}

/** 一条和除法完全无关的路：C(n) = C(2n, n) − C(2n, n+1)（杨辉三角推出来） */
static ll byDiff(int n) {
    static ll C[2 * NMAX + 1][2 * NMAX + 2];
    for (int i = 0; i <= 2 * n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        for (int j = i + 1; j <= 2 * n + 1; j++) C[i][j] = 0;
    }
    return C[2 * n][n] - C[2 * n][n + 1];
}

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

    int firstFactBad = -1, firstIntBad = -1, diffBad = 0, exactBad = 0;
    ll maxMid18 = 0, opsRec18 = 0, opsClosed18 = 0, ans18 = 0;

    if (!csv) printf("  n        答案 f(n)      ③ 递推       ★ ④ 闭形式    ✗ 三个阶乘    ✗ 闭形式用 int   闭形式的最大中间值\n");
    for (int n = 1; n <= NMAX; n++) {
        ll opsR = 0, opsC = 0, mx = 0; bool exact = true;
        ll r = rec(n, &opsR);
        ll c = closed(n, &opsC, &mx, &exact);
        ll f = byFact(n);
        unsigned it = byInt(n);
        ll d = byDiff(n);
        if (!exact) exactBad++;
        if (d != r) diffBad++;
        if (f != r && firstFactBad < 0) firstFactBad = n;
        if ((ll)it != r && firstIntBad < 0) firstIntBad = n;
        if (n == NMAX) { maxMid18 = mx; opsRec18 = opsR; opsClosed18 = opsC; ans18 = r; }
        if (!csv)
            printf("%3d %16lld %12lld %12lld %13lld %14u %20lld\n", n, r, r, c, f, it, mx);
    }

    if (csv) {
        printf("firstFactBad,%d\n", firstFactBad);
        printf("firstIntBad,%d\n", firstIntBad);
        printf("diffBad,%d\n", diffBad);
        printf("exactBad,%d\n", exactBad);
        printf("ans18,%lld\n", ans18);
        printf("maxMid18,%lld\n", maxMid18);
        printf("intTop,%lld\n", 2147483647LL);
        printf("midOverInt,%.2f\n", (double)maxMid18 / 2147483647.0);
        printf("ansUnderInt,%s\n", ans18 <= 2147483647LL ? "yes" : "no");
        printf("opsRec18,%lld\n", opsRec18);
        printf("opsClosed18,%lld\n", opsClosed18);
        return 0;
    }

    printf("\n① 三条溢出线（题面 n ≤ 18，18 个值全试过）\n");
    printf("   ✗ 三个阶乘各算一遍     第一个算错的 n = **%d**（2n = %d ⇒ 21! 装不下 long long）\n",
           firstFactBad, 2 * firstFactBad);
    printf("   ✗ 闭形式但用 32 位     第一个算错的 n = **%d**\n", firstIntBad);
    printf("   ★ 闭形式 + long long   18 个值**全对**\n");

    printf("\n② n = 18 那一格：答案装得下 int，中间值装不下\n");
    printf("   答案            %13lld   %s int（上限 2147483647）\n", ans18, ans18 <= 2147483647LL ? "≤" : ">");
    printf("   最大中间值      %13lld   是 int 上限的 **%.2f 倍**\n", maxMid18, (double)maxMid18 / 2147483647.0);
    printf("   ⇒ ★★ 前三版从来不算 C(2n,n)，它们的每个中间量都 ≤ 答案 —— **换一条路就换一套溢出账**\n");

    printf("\n③ 两条自检\n");
    printf("   「边乘边除每一步都整除」除不尽的 n：**%d 个**（前 i 步之后正好是 C(n+i, i)）\n", exactBad);
    printf("   一条和除法无关的路 C(2n,n) − C(2n,n+1)，和递推对不上的 n：**%d 个**\n", diffBad);

    printf("\n④ 次数（n = 18）\n");
    printf("   ③ 卡特兰递推   %lld 次乘法（O(n²)）\n", opsRec18);
    printf("   ★ ④ 闭形式     %lld 次乘法（O(n)）—— 而两版都是一瞬间，选它的理由是「一行说得清」\n", opsClosed18);
    return 0;
}