P1464 Function · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1464，日期见页头。两边不一致时信原站。

题目描述

对于一个递归函数 w(a, b, c)：

如果 a ≤ 0 或 b ≤ 0 或 c ≤ 0 就返回值 1。
如果 a > 20 或 b > 20 或 c > 20 就返回 w(20, 20, 20)。
如果 a < b 并且 b < c 就返回 w(a,b,c-1) + w(a,b-1,c-1) − w(a,b-1,c)。
其它的情况就返回 w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) − w(a-1,b-1,c-1)。

这是个简单的递归函数，但实现起来可能会有些问题。当 a、b、c 均为 15 时， 调用的次数将非常的多。你要想个办法才行。

注意：例如 w(30, -1, 0) 又满足条件 1 又满足条件 2， 请按照最上面的条件来算，答案为 1。

输入格式：会有若干行，并以 -1 -1 -1 结束。

输出格式：输出若干行，每一行格式 w(a, b, c) = ans。注意空格。

数据范围：保证输入的数在 [-2^63, 2^63 - 1] 之间，并且是整数。不包括 -1 -1 -1 的输入行数 T 满足 1 ≤ T ≤ 10^5。

1先看清楚：这道题不用你想算法

递归是题面直接给的，四条规则一字不差抄进代码就行。所以这道题考的完全不是「想出解法」，而是三件很具体的事：

① 跑得动吗          四条规则照抄，w(15,15,15) 要调用多少次？
② 规则的顺序对吗    题面专门举了 w(30,-1,0) 这个例子 —— 那句话就是分数
③ 读得对吗          输入范围到 2^63，用 int 读会悄悄截断

★ 这三件事没有一件是「算法」，但它们决定了这道题的全部分数。

输入

1 1 1
2 2 2
-1 -1 -1

输出

w(1, 1, 1) = 2
w(2, 2, 2) = 4

样例只有两行。注意输出格式里逗号后面有一个空格。 上面那段输出是仓库里的 p1464.cpp 真跑出来的。

2第 ① 版：把四条规则照抄一遍（对，但跑不完）

p1464Naive.cpp第 ① 版（跑不完）

先跑这两组。再把 8 8 8 改成 10 10 10 —— 会明显卡一下。题面点名的 15 15 15 就别试了。

// 洛谷 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;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

⚠ 题面自己都提醒了：「调用的次数将非常的多」

实测（第 ⑤ 步那张表）：

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）。

这条规律不影响做题，但它是个很重要的提醒： 答案很小，不代表算出它便宜。 w(10,10,10) 的答案只有 1024，却要走近五亿步。

3第 ② 版：加了记忆化，快了，但答案错了

加缓存这一步谁都会做。可这道题的坑不在缓存上 —— 在四条规则的顺序上。

题面把它写在明处了：

注意：例如 w(30, -1, 0) 又满足条件 1 又满足条件 2，请按照最上面的条件来算，答案为 1。

这一版故意把两条判断调了个个儿：

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

p1464Order.cpp第 ② 版（快，但答案错）

前两行（样例）全对。看第三行：它给 1048576，而正确答案是 1。

// 洛谷 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;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 这一课和递归无关，但值一整道题

当几条规则可能同时成立时，「先判哪一条」就是题目的一部分，不是实现细节。

题面特意举了个例子来说明顺序 —— 凡是题面专门举例说明的地方，都是分数所在。

⚠ 而且这个错极难自己发现：只要你的测试数据里没有「又是负数、又超过 20」的组合，它就一直是对的。样例正好没有这种组合。

⇒ 读题的时候，看到「又满足…又满足…请按照…」这种句子， 立刻回到代码里去数一遍 if 的顺序。

4第 ③ 版：顺序照题面来 + 记忆化 + 表跨询问保留（正解）

和前两版的差别一共三处，每一处对应一个真会挂人的地方：

① 加了记忆化              治第 ① 版的「跑不完」
② 规则顺序照题面来        治第 ② 版的「w(30,-1,0) 算错」
③ 缓存表跨询问保留        治一个前两版都看不出来的问题

★ 第 ③ 条：为什么表不能每次询问清一遍

题目最多有 10^5 行询问。如果每读一行就 memset 一次表，等于每一行都从零开始重算 —— 记忆化白加。

而 w 是个纯函数：w(3,4,5) 是多少，跟前面问过什么毫无关系。 ⇒ 表本来就该一直留着，问得越多越划算。

★ 一般化一句：缓存能不能跨询问复用，取决于「这个函数的答案会不会随外部状态变」。 纯函数就能。这个判断以后会一直用。

⚠ 第 ③ 条之外还有一个读入的坑

题面写着数值范围是 [-2^63, 2^63 - 1] ⇒ 必须用 long long 读。

用 int 读的话，一个 30000000000 会被悄悄截断成一个完全不同的数，程序不报任何错，只是答案不对。

⚠ 但下标仍然是 int：clamp 到 20 之后最大就是 20，别把数组开成 long long 索引 —— 那是另一种误解。

p1464.cpp第 ③ 版（正解）

第 ① 版跑不完的 15 15 15，这一版一瞬间；而 30 -1 0 也给出正确的 1。

// 洛谷 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;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

5换一把可复现的尺子：加不加记忆化差多少

p1464Count.cpp数次数

不用输入，直接跑（第 1 列到 n=10 要四亿多次调用，会跑一秒左右）。

// P1464 加不加记忆化，差多少 —— 换一把可复现的尺子
//
// 输入：无（表是写死的几组 (n,n,n)）
// 输出：一张表，对每组列出
//         答案 w(n,n,n)
//         1.没记忆化      调用了多少次 w()
//         2.有记忆化      调用了多少次（含直接命中缓存的）
//         真正算的格子     有多少个 (a,b,c) 被真的算了一遍
//
// ★ 两件事值得看：
//   ① **答案本身很小**（w(n,n,n) 正好是 2^n），可算出它要走的路却是天文数字 ——
//      「答案小」和「好算」完全是两回事。
//   ② 最后一列**永远不超过 20×20×20 = 8000** —— 状态就三个量，每个不超过 20。
//      这就是「该不该上记忆化」的全部判断依据。
//
// ⚠ 第 1 列到 n = 10 已经是四亿多次调用（这份程序因此要跑两三秒）。
//   题面里点名的 w(15,15,15) 就不在表里了 —— 它跑不完。

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

long long naiveCalls = 0;
long long naive(long long a, long long b, long long c) {
    naiveCalls++;
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return naive(20, 20, 20);
    if (a < b && b < c) return naive(a, b, c - 1) + naive(a, b - 1, c - 1) - naive(a, b - 1, c);
    return naive(a - 1, b, c) + naive(a - 1, b - 1, c) + naive(a - 1, b, c - 1) - naive(a - 1, b - 1, c - 1);
}

long long memo[21][21][21];
bool has[21][21][21];
long long memoCalls = 0, memoFilled = 0;

long long withMemo(long long a, long long b, long long c) {
    memoCalls++;
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return withMemo(20, 20, 20);
    int x = (int)a, y = (int)b, z = (int)c;
    if (has[x][y][z]) return memo[x][y][z];
    memoFilled++;
    long long r;
    if (a < b && b < c) r = withMemo(a, b, c - 1) + withMemo(a, b - 1, c - 1) - withMemo(a, b - 1, c);
    else r = withMemo(a - 1, b, c) + withMemo(a - 1, b - 1, c) + withMemo(a - 1, b, c - 1) - withMemo(a - 1, b - 1, c - 1);
    has[x][y][z] = true;
    return memo[x][y][z] = r;
}

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

    for (int n : {1, 2, 5, 8, 10}) {
        naiveCalls = 0;
        long long ans = naive(n, n, n);

        memset(has, 0, sizeof has);
        memoCalls = memoFilled = 0;
        withMemo(n, n, n);

        cout << setw(5) << n
             << setw(16) << ans
             << setw(15) << naiveCalls
             << setw(13) << memoCalls
             << setw(14) << memoFilled << "\n";
    }

    cout << "\n答案那一列正好是 2^n —— 答案小，不代表算出它便宜。\n";
    cout << "最后一列永远不超过 20*20*20 = 8000，因为状态就三个量、每个不超过 20。\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

    n   答案 w(n,n,n)     1.没记忆化   2.有记忆化  真正算的格子
-----   -------------   ------------   ----------   -----------
    1               2              5            5             1
    2               4             21           21             5
    5              32           5237          211            55
    8             256        4464671          761           204
   10            1024      489048226         1421           385

答案那一列正好是 2^n —— 小得可怜，可算它要走的路是天文数字。
最后一列永远不超过 20 × 20 × 20 = 8000，因为状态就三个量、每个不超过 20。这就是「该不该上记忆化」的全部判断依据。
第 1 列和最后一列在 n = 10 时差了 一百二十多万倍。

★ 三道题，同一个判断

P1028 状态一个量、P1044 两个量、这道题三个量 —— 判断方法从头到尾没变过：

一个子问题由哪几个量唯一决定？这几个量的组合有多少种？组合数够小就上记忆化。

⇒ 记住这句问法，比记住「哪些题能记忆化」有用得多。

6回头看：这道题在教什么

✓ 三件带得走的东西

题面给了递归，不等于题目简单。 这道题全部的分数在「跑得动 / 顺序对 / 读得对」上，没有一件是算法。
题面专门举的例子，就是坑的位置。 看到「又满足…又满足…请按照…」，立刻回去数 if 的顺序。
纯函数的缓存可以跨询问复用。 10^5 行询问时，这一条和记忆化本身一样重要。