记录编号	606739	评测结果	AAAAAAAAAA
题目名称	3946.信使	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	7.693 s
提交时间	2025-10-02 20:49:15	内存使用	10.21 MiB

#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 walk d steps from i to j
ll h[MAXN][MAXN][MAXD]; // h[i][j][d]: tot solution of walk d steps from i to j without passing i or j
ll g[MAXN][MAXN][MAXD]; // g[i][j][d]: tot solution of walk d steps from i to i without passing i or j
int e[MAXN][MAXN];
int n, m, q;
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;
        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;
}