记录编号	606655	评测结果	AAAAAAAAAA
题目名称	3946.信使	最终得分	100
用户昵称	123	是否通过	通过
代码语言	C++	运行时间	9.238 s
提交时间	2025-10-01 16:42:26	内存使用	10.69 MiB

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