记录编号	606670	评测结果	AAAAAAAAAA
题目名称	3946.信使	最终得分	100
用户昵称	Ruyi	是否通过	通过
代码语言	C++	运行时间	3.796 s
提交时间	2025-10-01 17:23:10	内存使用	6.94 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=110,D=50;
int e[N][N],n,m,z,u,v,d,ans=0,f[N][N][55],h[N][N][55],g[N][N][55];
int main(){
    freopen("messenger.in","r",stdin);
    freopen("messenger.out","w",stdout);
    scanf("%d%d%d",&n,&m,&z);
    for(int i=1;i<=m;++i){
        int a,b;scanf("%d%d",&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<=D;++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<=D;++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]+1LL*g[i][j][k]*f[i][j][d-k]+1LL*h[i][j][k]*f[j][j][d-k])%z;
                    g[i][j][d]=(g[i][j][d]+1LL*g[i][j][k]*f[i][i][d-k]+1LL*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;
            }
    int q;scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&u,&v,&d);
        printf("%d\n",h[u][v][d]);
    }
    return 0;
}