这个问题可以看作是一个路径计数问题。由于列车只能从小编号城市开往大编号城市，整个图是一个有向无环图(DAG)，我们可以使用动态规划来解决。

动态规划解法 状态定义 设 dp[i] 表示从城市 $i$ 出发的所有不同旅程的数量（包括只包含城市 $i$ 本身的旅程）。

状态转移 对于城市 $i$，我们可以：

只停留在城市 $i$（计为 $1$ 种旅程）

乘坐列车前往任意可达的城市 $j$，然后从 $j$ 继续旅程

因此状态转移方程为：

text dp[i] = 1 + ∑ dp[j] 对于所有从 i 可达的 j 计算顺序 由于列车只能从小编号城市前往大编号城市，我们应该从大到小计算 dp 值，即从城市 $N$ 计算到城市 $1$。

算法实现 基础版本 最直接的方法是对于每个城市 $i$，枚举所有可能的 $t$ 值：

python dp = [0] * (N + 1) dp[N] = 1 # 最后一个城市只有一种旅程：自身

for i in range(N - 1, 0, -1): if d[i] == 0: # 列车停运 dp[i] = 1 else: dp[i] = 1 # 自身 t = 1 while t <= x[i] and i + t * d[i] <= N: j = i + t * d[i] dp[i] = (dp[i] + dp[j]) % MOD t += 1 优化考虑 当 $d_i$ 很小而 $x_i$ 很大时，直接枚举 $t$ 可能会超时。需要进行优化：

当 $d_i$ 较大时，循环次数很少

当 $d_i$ 较小时，可以使用前缀和等技巧加速求和