题目理解

我们有一个 $n$ 个节点的有向图，要求计算从起点 $u$ 到终点 $v$ 恰好经过 $d$ 条边的路径数量，其中：

• 起点和终点各只访问一次
• 中间节点可以重复访问
• 边可以重复经过

问题转化

设 $g[s][t][d]$ 表示从 $s$ 到 $t$ 恰好走 $d$ 步的路径总数（允许重复访问所有节点）。

但题目要求起点和终点各只访问一次，这意味着：

• 路径中不能提前到达终点（否则终点就访问了多次）
• 路径中不能提前回到起点（否则起点就访问了多次）

关键定义

代码中定义了四个关键数组：

1. $g[s][t][d]$: 从 $s$ 到 $t$ 走 $d$ 步的路径总数（无限制）
2. $f[s][t][d]$: 从 $s$ 到 $t$ 走 $d$ 步，且只在最后一步到达 $t$（终点只访问一次）
3. $e[s][t][d]$: 从 $s$ 回到 $s$ 走 $d$ 步，且不经过 $t$
4. $h[s][t][d]$: 从 $s$ 回到 $s$ 走 $d$ 步，不经过 $t$，且起点只访问两次（开始和结束）

递推关系

1. 基础计数 $g[s][t][d]$

g[x][x][0] = 1;
for (int d = 1; d <= D; d++) {
    for (int i = 1; i <= n; i++) {
        for (auto u : v[i]) {
            g[x][u][d] += g[x][i][d - 1];
        }
    }
}

这就是简单的路径计数：$g[s][t][d] = \sum_{u \to t} g[s][u][d-1]$

2. 终点只出现一次 $f[s][t][d]$

f[s][t][d] = g[s][t][d];
for (int j = 1; j < d; j++) {
    f[s][t][d] = (f[s][t][d] - f[s][t][j] * g[t][t][d - j]) % Mod;
}

这里用容斥原理：从所有路径中减去那些提前到达终点的路径。

• $f[s][t][j]$: 第一次到达 $t$ 是在第 $j$ 步
• $g[t][t][d-j]$: 从 $t$ 开始在剩下的 $d-j$ 步中随意走（可能多次回到 $t$）

3. 不经过终点的环 $e[s][t][d]$

e[s][t][d] = g[s][s][d];
for (int j = 1; j < d; j++) {
    e[s][t][d] = (e[s][t][d] - f[s][t][j] * g[t][s][d - j]) % Mod;
}

从所有回到 $s$ 的路径中，减去那些经过 $t$ 的路径。

4. 起点只出现两次的环 $h[s][t][d]$

h[s][t][d] = e[s][t][d];
for (int j = 1; j < d; j++) {
    h[s][t][d] = (h[s][t][d] - h[s][t][j] * e[s][t][d - j]) % Mod;
}

用容斥确保起点只在开始和结束出现：从所有不经过 $t$ 的环中，减去那些中间回到起点的环。

5. 最终答案 $ans[s][t][d]$

ans[s][t][d] = f[s][t][d];
for (int j = 1; j < d; j++) {
    ans[s][t][d] = (ans[s][t][d] - h[s][t][j] * f[s][t][d - j]) % Mod;
}

从终点只出现一次的路径中，减去那些中间回到起点的路径（因为起点只能出现一次）。

算法流程

1. 预处理 $g$ 数组：对每个起点 $s$，计算到所有节点走 $0$ 到 $D$ 步的路径数
2. 递推计算 $f, e, h, ans$ 数组
3. 处理查询：直接输出 $ans[u][v][d]$

时间复杂度

• 预处理 $g$: $O(n \cdot m \cdot D)$
• 递推 $f,e,h,ans$: $O(n^2 \cdot D^2)$
• 查询: $O(1)$

由于 $n \leq 100$, $D \leq 50$，这在时间限制内可行。

算法标签

• 动态规划
• 容斥原理
• 递推
• 图结构

总结

该算法通过巧妙的容斥和递推关系，解决了带有起点终点访问次数限制的固定长度路径计数问题。核心思想是将复杂约束分解为多个子问题，逐步应用容斥原理得到最终答案。