3946. 信使 题解

题目描述

给定一个 $n$ 个点 $m$ 条边的有向图，$q$ 次询问从点 $u$ 走 $d$ 步到达点 $v$，且只经过点 $u,v$ 各一次的路径数。答案对 $z$ 取模。

题解

原题目要求只经过起点和终点一次的路径数，这个不太好求。但是如果没有这个限制，只要求任意两点之间走 $d$ 步的路径数的话，还是很好求哒！

设 $f[i][j][d]$ 表示：从点 $i$ 走 $d$ 步无限制到达点 $j$ 的路径数。

for (int i = 1; i <= n; ++i)
   for (int j = 1; j <= n; ++j) if (e[i][j])
       f[i][j][1] = 1;
for (int d = 1; d <= 50; ++d)
   for (int i = 1; i <= n; ++i)
       for (int j = 1; j <= n; ++j)
           for (int k = 1; k <= n; ++k) if (e[k][j])
               f[i][j][d] = (f[i][j][d] + f[i][k][d - 1]);

那么要求从点 $i$ 走 $d$ 步不经过点 $i,j$ 到达点 $j$ 的路径数，就转化为了从点 $i$ 走 $d$ 步无限制到达点 $j$ 的路径数减去从点 $i$ 走 $d$ 步中途经过了点 $i$ 或点 $j$ 到达点 $j$ 的路径数
........................................................................

该题解待审