记录编号	606681	评测结果	AAAAAAAAAA
题目名称	3946.信使	最终得分	100
用户昵称	hsl_beat	是否通过	通过
代码语言	C++	运行时间	10.476 s
提交时间	2025-10-01 21:12:57	内存使用	9.69 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, mod;
int dp1[111][111][55]; 
int dp2[111][111][55]; 
int ans[111][111][55]; 
signed main()
{
    freopen("messenger.in", "r", stdin);
    freopen("messenger.out", "w", stdout);
    cin >> n >> m >> mod;
    vector<vector<int>> w(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        w[u][v] = 1;
    }
    for (int i = 1; i <= n; i++) {
        dp1[i][i][0] = 1;
    }
    for (int len = 1; len <= 50; len++) {
        for (int k = 1; k <= n; k++) {  
            for (int i = 1; i <= n; i++) {  
                for (int j = 1; j <= n; j++) {  
                    if (w[k][j]) { 
                        dp1[i][j][len] = (dp1[i][j][len] + dp1[i][k][len - 1]) % mod;
                    }
                }
            }
        }
    }
    for (int len = 0; len <= 50; len++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    continue;
                }
                ans[i][j][len] = dp1[i][j][len];
                dp2[i][j][len] = dp1[i][i][len];
                for (int k = 1; k < len; k++) {
                    dp2[i][j][len] = (dp2[i][j][len] - ans[i][j][k] * dp1[j][i][len - k] % mod  - dp2[i][j][k] * dp1[i][i][len - k] % mod + 2*mod) % mod;
                    ans[i][j][len] = (ans[i][j][len] - dp2[i][j][k] * dp1[i][j][len - k] % mod  - ans[i][j][k] * dp1[j][j][len - k] % mod + 2*mod) % mod;
                }
            }
        }
    }
    
    int T;
    cin >> T;
    while (T--) {
        int u, v, k;
        cin >> u >> v >> k;
        cout << ans[u][v][k] << '\n';
    }
    return 0;
}