记录编号	584935	评测结果	AAAAAAAAAA
题目名称	信使	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	8.521 s
提交时间	2023-11-17 07:33:26	内存使用	14.74 MiB

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;    
    ll n,m,s,z,ans=0,flag=0;
    ll e[110][110];
    ll f[110][110][55],g[110][110][55],h[110][110][55];
    int main(){
        freopen("messenger.in","r",stdin);
        freopen("messenger.out","w",stdout);
          cin>>n>>m>>z;
          for(int i=1;i<=m;i++){
              int a,b;
              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][k][d-1];
                          f[i][j][d]%=z;
                          //dp出点i到j的方案数 
                      }
                  }
              }
          }
          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++){
                          //g和h中先存储的是不合法的方案数
                          h[i][j][d]=(h[i][j][d]+(long long)g[i][j][k]*f[i][j][d-k]+(long long)h[i][j][k]*f[j][j][d-k])%z;
                          g[i][j][d]=(g[i][j][d]+(long long)g[i][j][k]*f[i][i][d-k]+(long long)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;
          cin>>q;
          while(q--){
          int a,b,c;
          cin>>a>>b>>c;
          cout<<h[a][b][c]<<endl;          
          }
          return 0;
    }