洛谷 P1464 Function

// P1464 —— 把 w 的展开打出来看：这个函数到底在算什么，以及为什么它慢
//
// 输入：无
// 输出：三段
//   ① w(1,1,1) 的完整展开（四项都直接命中规则 1，手算就能跟完）
//   ② w(2,2,2) 的完整展开（多了一层，形状和 ① 一样）
//   ③ 算 w(5,5,5) 时，同一个 (a,b,c) 被**重新算了多少遍** —— 这就是记忆化的全部理由
//
// ★ 这份程序不解题，它只回答一个问题：**看不懂题面的时候，先手算一次。**
//   w(a,b,c) 没有任何现实意义，它就是四条规则；而四条规则里到底走哪一条，
//   只有把一层层展开摆出来才看得见。
//
// ⚠ 规则的判定顺序和正解完全一致（规则 1 排最前）—— 否则这张展开图就是错的。

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

/** 判断 (a,b,c) 该走哪条规则，返回 1~4。 */
int ruleOf(int a, int b, int c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return 2;
    if (a < b && b < c) return 3;
    return 4;
}

/**
 * 规则 3 / 4 各自的子问题，连同它前面的符号。
 * ⚠ 两条规则的项数**不一样**：规则 3 是三项（两加一减），规则 4 是四项（三加一减）。
 *   最早写这份程序时把规则 3 也当成四项，w(5,5,5) 就成了 124（正确是 32）—— 展开图会整张骗人。
 */
vector<pair<int, array<int, 3>>> childrenOf(int a, int b, int c) {
    if (ruleOf(a, b, c) == 3)
        return {{+1, {a, b, c - 1}}, {+1, {a, b - 1, c - 1}}, {-1, {a, b - 1, c}}};
    return {{+1, {a - 1, b, c}}, {+1, {a - 1, b - 1, c}},
            {+1, {a - 1, b, c - 1}}, {-1, {a - 1, b - 1, c - 1}}};
}

long long w(int a, int b, int c) {
    int r = ruleOf(a, b, c);
    if (r == 1) return 1;
    if (r == 2) return w(20, 20, 20);
    long long s = 0;
    for (auto& [sign, t] : childrenOf(a, b, c)) s += sign * w(t[0], t[1], t[2]);
    return s;
}

string name(int a, int b, int c) {
    return "w(" + to_string(a) + "," + to_string(b) + "," + to_string(c) + ")";
}

/** 缩进打印一棵展开树。depth 只是缩进用；叶子（规则 1）直接打 = 1。 */
void show(int a, int b, int c, int depth) {
    string pad(depth * 2, ' ');
    int r = ruleOf(a, b, c);
    if (r == 1) {
        cout << pad << name(a, b, c) << " = 1        <- 规则 1（有一个数 <= 0）\n";
        return;
    }
    auto ch = childrenOf(a, b, c);
    cout << pad << name(a, b, c) << " = ";
    for (size_t i = 0; i < ch.size(); i++) {
        cout << (i == 0 ? "" : (ch[i].first < 0 ? " - " : " + "))
             << name(ch[i].second[0], ch[i].second[1], ch[i].second[2]);
    }
    cout << "        <- 规则 " << r << "\n";
    for (auto& [sign, t] : ch) show(t[0], t[1], t[2], depth + 1);
    cout << pad << name(a, b, c) << " = " << w(a, b, c) << "\n";
}

int main() {
    cout << "① 展开 w(1,1,1)：四项全都撞上规则 1，一步到底\n\n";
    show(1, 1, 1, 0);

    cout << "\n② 展开 w(2,2,2)：多一层，形状和上面一模一样\n\n";
    show(2, 2, 2, 0);

    // ③ 子问题重叠：算 w(5,5,5) 的过程里，同一个 (a,b,c) 被重新算了几遍
    map<array<int, 3>, long long> cnt;
    // 这里不能调用上面的 w()（它不记次数），单独写一份带计数的
    function<long long(int, int, int)> count = [&](int a, int b, int c) -> long long {
        cnt[{a, b, c}]++;
        int r = ruleOf(a, b, c);
        if (r == 1) return 1;
        if (r == 2) return count(20, 20, 20);
        long long s = 0;
        for (auto& [sign, t] : childrenOf(a, b, c)) s += sign * count(t[0], t[1], t[2]);
        return s;
    };
    long long ans = count(5, 5, 5);

    long long total = 0;
    for (auto& [k, v] : cnt) total += v;
    vector<pair<long long, array<int, 3>>> top;
    for (auto& [k, v] : cnt) top.push_back({v, k});
    sort(top.rbegin(), top.rend());

    cout << "\n③ 算 w(5,5,5) = " << ans << " 的过程里，一共调用了 " << total << " 次 w()，\n";
    cout << "   而不同的 (a,b,c) 只有 " << cnt.size() << " 个。被重算最多的五个：\n\n";
    for (int i = 0; i < 5 && i < (int)top.size(); i++) {
        cout << "   " << name(top[i].second[0], top[i].second[1], top[i].second[2])
             << " 被算了 " << top[i].first << " 遍\n";
    }
    cout << "\n   " << total << " 次调用 / " << cnt.size() << " 个不同的子问题"
         << " —— 重复的那些，就是记忆化省下来的。\n";
    return 0;
}

// 洛谷 P1464 Function —— 第 ① 版：把题面上那四条规则照抄成代码（对，但跑不完）
//
// 输入：若干行 a b c，以 -1 -1 -1 结束
// 输出：每行 "w(a, b, c) = ans"
//
// 这份为什么存在：这道题的递归**是题面直接给的**，一个字都不用自己想 ——
// 所以它是「照着写就完事了吗」这个问题最干净的一次反例。
//
// ⚠ 它慢得非常夸张，而且题面自己都提醒了：「当 a,b,c 均为 15 时，调用的次数将非常的多」。
//    实测（p1464Count.cpp 跑出来的）：
//        w(8,8,8)     4 464 671 次
//        w(10,10,10)  489 048 226 次
//        w(12,12,12)  56 533 377 950 次
//    而题目允许有 10^5 行询问。⇒ 一行都跑不完。
//
// ★ 顺带一个跑出来才看见的规律：**w(n,n,n) 正好是 2^n**（2、4、32、256、1024、4096）。
//   知道这条不影响做题，但它是个提醒：**答案很小，不代表算出它很便宜。**

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

long long w(long long a, long long b, long long c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;              // ★ 这一条必须排在最前面，见第 ③ 版
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
    if (a < b && b < c) return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}

int main() {
    long long a, b, c;
    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
    }
    return 0;
}

// 洛谷 P1464 Function —— 第 ② 版：加了记忆化，快了，**但答案错了**
//
// 输入 / 输出：同第 ① 版
//
// 这份为什么存在：记忆化本身（解析页第 ④ 步）加对了，可**这道题的坑不在缓存上，
// 在四条规则的顺序上** —— 这一版就是「速度已经够了、答案却错了」的样子。
//
// 题面把这个坑写在明处了：
//   「注意：例如 w(30,-1,0) 又满足条件 1 又满足条件 2，请按照最上面的条件来算，答案为 1。」
//
// 而这一版故意把两条判断调了个个儿 —— 先看「有没有超过 20」，再看「有没有小于等于 0」：
//
//     if (a > 20 || b > 20 || c > 20) ...        <- 错：它把 (30,-1,0) 抢走了
//     if (a <= 0 || b <= 0 || c <= 0) return 1;
//
// ⇒ w(30,-1,0) 会被当成 w(20,20,20) 来算，得到 1048576，而正确答案是 1。
//
// ★★ 这一版最值钱的一课和递归无关：
//   **当几条规则可能同时成立时，「先判哪一条」就是题目的一部分，不是实现细节。**
//   题面特意举了个例子来说明顺序，那句话就是分数所在。
//
// ⚠ 而且这个错**很难自己发现**：只要你的测试数据里没有「又负又超 20」的组合，它就一直是对的。

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

long long memo[21][21][21];
bool has[21][21][21];

long long w(long long a, long long b, long long c) {
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);   // ⚠ 顺序反了
    if (a <= 0 || b <= 0 || c <= 0) return 1;

    int x = (int)a, y = (int)b, z = (int)c;
    if (has[x][y][z]) return memo[x][y][z];
    long long r;
    if (a < b && b < c) r = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    else r = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    has[x][y][z] = true;
    return memo[x][y][z] = r;
}

int main() {
    long long a, b, c;
    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
    }
    return 0;
}

// 洛谷 P1464 Function —— 第 ③ 版：记忆化 + 规则顺序照题面来（正解）
//
// 输入：若干行 a b c，以 -1 -1 -1 结束（最多 10^5 行）
// 输出：每行 "w(a, b, c) = ans"，注意逗号后面有空格
//
// 和前两版的差别，一共就三处，每一处都对应一个真会挂人的地方：
//
//   ① 加了记忆化              —— 治第 ① 版的「跑不完」
//   ② 规则顺序照题面来        —— 治第 ② 版的「w(30,-1,0) 算错」
//   ③ 缓存表**跨询问保留**    —— 治一个前两版都看不出来的问题：
//      题目最多有 10^5 行询问，每行都清一次表的话，等于记忆化白加。
//      而 w 是个纯函数，答案跟前面问过什么毫无关系 ⇒ 表本来就该一直留着。
//
// ⚠ 输入必须用 long long：题面写着数值范围是 [-2^63, 2^63-1]。
//   用 int 读的话，一个 30000000000 会被截成一个完全不同的数，而程序不会有任何反应。
//   ⇒ 但**下标**仍然是 int（clamp 到 20 之后最大就是 20），别把数组开成 long long 索引。

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

long long memo[21][21][21];
bool has[21][21][21];                    // ★ 全局，跨询问保留

long long w(long long a, long long b, long long c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;               // ★ 规则 1 必须排最前
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);   // ★ 规则 2

    int x = (int)a, y = (int)b, z = (int)c;
    if (has[x][y][z]) return memo[x][y][z];

    long long r;
    if (a < b && b < c) r = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    else r = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);

    has[x][y][z] = true;
    return memo[x][y][z] = r;
}

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

    long long a, b, c;
    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
    }
    return 0;
}