文字教学

这是一道拓扑排序+动态规划问题，核心是在有向无环图（DAG）上统计从生产者到顶级消费者的路径数。

1. 图的存储：用链式前向星存图，效率高且符合竞赛风格。
2. 拓扑排序：食物网是DAG，按拓扑序处理节点，保证处理一个节点时，所有指向它的节点（它的食物）都已处理完。
3. 动态规划：设 dp[i] 表示以 i 为终点的食物链数量。初始时，生产者（入度为0）的 dp 值为1。对于边 u→v（u被v吃），更新 dp[v] = (dp[v] + dp[u]) % 80112002。
4. 最终答案：所有顶级消费者（出度为0）的 dp 值之和，再取模。

代码

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

const int MOD = 80112002;
const int N = 5005;
const int M = 500005;

int hd[N], ed[M], nt[M], cnt;
int in[N], out[N], dp[N];
int q[N], fr, rr;

void add(int u, int v) {
    ed[++cnt] = v;
    nt[cnt] = hd[u];
    hd[u] = cnt;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        in[b]++;
        out[a]++;
    }
    fr = rr = 0;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 0) {
            dp[i] = 1;
            q[rr++] = i;
        } else {
            dp[i] = 0;
        }
    }
    while (fr < rr) {
        int u = q[fr++];
        for (int i = hd[u]; i; i = nt[i]) {
            int v = ed[i];
            dp[v] = (dp[v] + dp[u]) % MOD;
            in[v]--;
            if (in[v] == 0) {
                q[rr++] = v;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (out[i] == 0) {
            ans = (ans + dp[i]) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}