洛谷 P4017 最大食物链计数

// ★★ P4017 正解：**拓扑序上的计数 DP**。
//
//   f[v] = 从任意一个「生产者」走到 v 的路径条数
//   · 生产者 = **入度为 0** 的点（不捕食别人）⇒ f = 1；
//   · 其余点 f[v] = Σ f[u]（u → v 的所有前驱）；
//   · 答案 = Σ f[v]，v 取遍**出度为 0** 的点（不被别人吃）。
//
// ⇒ 两句话要一起读：「最左端是生产者、最右端是消费者」——
//   **初值只给入度为 0 的点、答案只收出度为 0 的点**，两头都不能放宽（本页两个错法各错一头）。
//
// ⚠ 模数是 **80112002**，不是那个眼熟的 10⁹+7。
//   ★ 而它顺带把「要不要 long long」这道算术题的答案定了：
//     两个模数以下的数相加 < 2 × 8.0112 × 10⁷ < 2³¹ ⇒ **int 就够**（本页第 ⑤ 步量了）。
//
// 复杂度 O(n + m)。顶格 n = 5 × 10³、m = 5 × 10⁵。
// ⚠ 题面【补充说明】保证「数据中不会出现环」—— 所以不用为判环额外写什么。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 80112002;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;                                // a 被 b 吃 ⇒ 边 a → b
        g[a].push_back(b);
        indeg[b]++;
        outdeg[a]++;
    }

    vector<int> f(n + 1, 0);
    vector<int> box;
    for (int i = 1; i <= n; i++)
        if (!indeg[i]) { box.push_back(i); f[i] = 1; }   // ★ 只有生产者的初值是 1
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) {
            f[v] = (f[v] + f[u]) % MOD;
            if (--indeg[v] == 0) box.push_back(v);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (!outdeg[i]) ans = (ans + f[i]) % MOD;      // ★ 只收顶端消费者
    printf("%lld\n", ans);
    return 0;
}

// ✗ P4017 错法一：**所有点的初值都设成 1**（不只是生产者）。
//
// 题面那句「最左端是**不会捕食其他生物的生产者**」被漏掉了半句。
// 于是每个点都白得一条「从自己开始」的链 ⇒ 它数的是**所有路径**，
// 而不是「从生产者到消费者」的路径。
//
// ★ 它多算 ⇒ 答案**恒 ≥ 正解**（在不取模的意义上）。解析页第 ③ 步量了这一条。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 80112002;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;                                // a 被 b 吃 ⇒ 边 a → b
        g[a].push_back(b);
        indeg[b]++;
        outdeg[a]++;
    }

    vector<int> f(n + 1, 0);
    vector<int> box;
    for (int i = 1; i <= n; i++) {
        if (!indeg[i]) box.push_back(i);
        f[i] = 1;                                        // ★ 每个点都给了 1
    }
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) {
            f[v] = (f[v] + f[u]) % MOD;
            if (--indeg[v] == 0) box.push_back(v);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (!outdeg[i]) ans = (ans + f[i]) % MOD;      // ★ 只收顶端消费者
    printf("%lld\n", ans);
    return 0;
}

// ✗ P4017 错法二：**答案把每个点的 f 都加了进去**（不只出度为 0 的）。
//
// 漏掉的是题面另外半句：「最右端是**不会被其他生物捕食的消费者**」。
// 于是每一条「走到一半」的链也被算成了一条食物链。
//
// ★ 同样是多算 ⇒ 恒 ≥ 正解。
// ⇒ ★★ 两个错法各错一头（一个放宽了左端、一个放宽了右端）——
//   这正是[第 26 章那条判据](/sol/p1220/)：**解一个放宽了的问题 ⇒ 答案只会偏大。**

#include <bits/stdc++.h>
using namespace std;
const int MOD = 80112002;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;                                // a 被 b 吃 ⇒ 边 a → b
        g[a].push_back(b);
        indeg[b]++;
        outdeg[a]++;
    }

    vector<int> f(n + 1, 0);
    vector<int> box;
    for (int i = 1; i <= n; i++)
        if (!indeg[i]) { box.push_back(i); f[i] = 1; }   // ★ 只有生产者的初值是 1
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) {
            f[v] = (f[v] + f[u]) % MOD;
            if (--indeg[v] == 0) box.push_back(v);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + f[i]) % MOD;                      // ★ 每个点都收了
    printf("%lld\n", ans);
    return 0;
}

// ✗ P4017 错法三：**模数顺手写成了 10⁹+7**。
//
// 题面写的是 **80112002**（这是个很不常见的模数，正因为不常见才容易被手指头改成 10⁹+7）。
//
// ★ 它的抓获率有一条精确的等式：**被抓的轮数 ≡ 真实答案越过 80112002 的轮数**
//   —— 答案没到模数时，两个模数给出的结果一模一样。解析页第 ④ 步量了这一条。
// ⇒ 又一次[第 21 章 P1077](/sol/p1077/) 那条：**抓不到它的是「档位」，不是「轮数」。**

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;        // ★ 抄错了

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;                                // a 被 b 吃 ⇒ 边 a → b
        g[a].push_back(b);
        indeg[b]++;
        outdeg[a]++;
    }

    vector<int> f(n + 1, 0);
    vector<int> box;
    for (int i = 1; i <= n; i++)
        if (!indeg[i]) { box.push_back(i); f[i] = 1; }   // ★ 只有生产者的初值是 1
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) {
            f[v] = (f[v] + f[u]) % MOD;
            if (--indeg[v] == 0) box.push_back(v);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (!outdeg[i]) ans = (ans + f[i]) % MOD;      // ★ 只收顶端消费者
    printf("%lld\n", ans);
    return 0;
}

// ✗ P4017 错法四：**全程不取模** —— 路径条数是指数级的，`int` 顶不住。
//
// 题面那句「由于这个结果可能过大，你只需要输出总数模上 80112002 的结果」
// 已经把答案会有多大写在脸上了。
//
// ⚠ 这一版故意用 `unsigned int` 累加：溢出在 C++ 里对**无符号**类型是有定义的（绕回去），
//   于是这个错**每次跑都一样**、可复现（[第 45 章](/ch/45-estimate/)那条规矩）。
//   换成 `int` 就是未定义行为，本机跑一百遍可能都「正常」。
//
// ★ 解析页第 ⑤ 步量了它从多大开始出问题。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 80112002;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;                                // a 被 b 吃 ⇒ 边 a → b
        g[a].push_back(b);
        indeg[b]++;
        outdeg[a]++;
    }

    vector<unsigned> f(n + 1, 0);
    vector<int> box;
    for (int i = 1; i <= n; i++)
        if (!indeg[i]) { box.push_back(i); f[i] = 1; }   // ★ 只有生产者的初值是 1
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) {
            f[v] = f[v] + f[u];            // ★ 不取模
            if (--indeg[v] == 0) box.push_back(v);
        }
    }

    unsigned ans = 0;
    for (int i = 1; i <= n; i++)
        if (!outdeg[i]) ans = ans + f[i];              // ★ 也不取模
    printf("%u\n", ans % MOD);                        // 最后才补一次模，已经晚了
    return 0;
}