记录编号	606651	评测结果	AAAAAAAAAA
题目名称	3946.信使	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	11.351 s
提交时间	2025-10-01 16:38:58	内存使用	6.81 MiB

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=105,V=55;
int n,m,mod,q,w[N][N];
int f[N][N][V],g[N][N][V],h[N][N][V];
int main(){
	freopen("messenger.in","r",stdin);
	freopen("messenger.out","w",stdout);
	scanf("%d %d %d",&n,&m,&mod);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d %d",&u,&v);
		w[u][v]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(w[i][j])f[i][j][1]=h[i][j][1]=1;
		}
	}
	for(int k=2;k<=50;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int l=1;l<=n;l++){
					if(w[l][j]){
						f[i][j][k]+=f[i][l][k-1];
						f[i][j][k]%=mod;
					}
				}
			}
		}
	}
	for(int k=2;k<=50;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j)continue;
				long long x=0,y=0;
				for(int d=1;d<k;d++){
					x+=1ll*g[i][j][d]*f[i][j][k-d]%mod,x%=mod; // i->i->j 
					x+=1ll*h[i][j][d]*f[j][j][k-d]%mod,x%=mod; // i->j->j 
					y+=1ll*g[i][j][d]*f[i][i][k-d]%mod,y%=mod; // i->i->i 
					y+=1ll*h[i][j][d]*f[j][i][k-d]%mod,y%=mod; // i->j->i 
				}
				h[i][j][k]=(f[i][j][k]-x+mod)%mod;
				g[i][j][k]=(f[i][i][k]-y+mod)%mod;
			}
		}
	}
	for(int k=2;k<=50;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(i==j)continue;
                long long x=0,y=0;
                for(int d=1;d<k;++d){
					x+=1ll*g[i][j][d]*f[i][j][k-d]%mod,x%=mod; // i->i->j 
					x+=1ll*h[i][j][d]*f[j][j][k-d]%mod,x%=mod; // i->j->j 
					y+=1ll*g[i][j][d]*f[i][i][k-d]%mod,y%=mod; // i->i->i 
					y+=1ll*h[i][j][d]*f[j][i][k-d]%mod,y%=mod; // i->j->i 
 				}
 				h[i][j][k]=(f[i][j][k]-x+mod)%mod;
 				g[i][j][k]=(f[i][i][k]-y+mod)%mod;
 			}
 		}
 	}
	scanf("%d",&q);
	int u,v,k;
	while(q--){
		scanf("%d %d %d",&u,&v,&k);
		printf("%d\n",h[u][v][k]);
	}
	return 0;
}