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$ 的路径数。

简单来说就是，正难则反。合法的方案不好求，就用总方案减去不合法的方案。

设 $h[i][j][d]$ 表示：从点 $i$ 走 $d$ 步不经过点 $i,j$ 到达点 $j$ 的路径数 。想要不合法就在中途的第 $k$ 步（$1 \le k \lt d$）走到 $i$ 或 $j$ 即可。

那么从点 $i$ 走 $d$ 步中途经过点 $i$ 或点 $j$ 到达点 $j$ 的路径数 $x$ 即为：

$$x = g[i][j][k] * f[i][j][d - k] + h[i][j][k] * f[j][j][d - k]\quad(1 \le k \lt d)$$

那么 $h[i][j][d] = f[i][j][d] - x$。

接下来考虑如何计算 $g[i][j][d]$（从点 $i$ 走 $d$ 步不经过点 $i,j$ 到达点 $i$ 的路径数）。

同样地，考虑正难则反，求出不合法的路径数，再用总路径数减去不合法的路径数即可。

类似，想要不合法，只需要在中途的第 $k$ 步（$1 \le k \lt d$）走到点 $i$ 或点 $j$ 即可。

那么从点 $i$ 走 $d$ 步途中经过点 $i$ 或点 $j$ 到达点 $j$ 的路径数 $y$ 为：

$$y = g[i][j][k] * f[i][i][d - k] + h[i][j][k] * f[j][i][d - k] \quad (1 \le k \lt d)$$

那么 $g[i][j][d] = f[i][j][d] - y$。

这些操作都是在询问之前进行的，每次询问的时候直接输出 $h[u][v][d]$（从点 $u$ 走 $d$ 步不经过点 $u,v$ 到达点 $v$ 的路径数）即可。

代码

#include <iostream>
using namespace std;
typedef long long ll;

const int MAXN = 110;
const int MAXD = 60;

ll f[MAXN][MAXN][MAXD]; // f[i][j][d]: tot solution of from i to j with no condition
ll h[MAXN][MAXN][MAXD]; // h[i][j][d]: tot solution of from i to j without passing i or j
ll g[MAXN][MAXN][MAXD]; // g[i][j][d]: tot solution of from i to i without passing i or j

int n, m, q;
int e[MAXN][MAXN];
ll z;

int main() {
  freopen("messenger.in", "r", stdin);
  freopen("messenger.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(false), cout.tie(0);
  cin >> n >> m >> z;
  for (int i = 1, a, b; i <= m; ++i) {
    cin >> a >> b;
    e[a][b] = 1;
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (e[i][j]) f[i][j][1] = h[i][j][1] = 1;
    }
  }

  for (int d = 2; 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]) % z;
        }
      }
    }
  }

  for (int d = 2; d <= 50; ++d) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (i == j) continue;
        // store the illegal paths to h[][][] and g[][][] first
        for (int k = 1; k < d; ++k) {
          h[i][j][d] = (h[i][j][d] + g[i][j][k] * f[i][j][d - k] + h[i][j][k] * f[j][j][d - k]) % z;
          g[i][j][d] = (g[i][j][d] + g[i][j][k] * f[i][i][d - k] + h[i][j][k] * f[j][i][d - k]) % z;
        }
        h[i][j][d] = (f[i][j][d] - h[i][j][d] + z) % z;
        g[i][j][d] = (f[i][i][d] - g[i][j][d] + z) % z;
      }
    }
  }

  cin >> q;
  for (int u, v, d; q--; ) {
    cin >> u >> v >> d;
    cout << h[u][v][d] << endl;
  }
  return 0;
}