记录编号	584871	评测结果	AAAAAAAAAA
题目名称	信使	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	6.635 s
提交时间	2023-11-16 16:07:23	内存使用	15.68 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
int n,m,z,q;
int e[N][N];
ll f[N][N][60],g[N][N][60],h[N][N][60];
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 x,y;
        scanf("%d%d",&x,&y);
        e[x][y] = 1;
        f[x][y][1] = 1;h[x][y][1] = 1;
    }
    for(int i = 2;i <= 50;i++)
        for(int x = 1;x <= n;x++)
            for(int y = 1;y <= n;y++)
                for(int k = 1;k <= n;k++)
                    if(e[k][y])f[x][y][i] = (f[x][y][i] + f[x][k][i-1]) % z;
    //正常dp 未减去经过x,y点的不合法方案数
    for(int i = 2;i <= 50;i++){
        for(int x = n;x >= 1;x--)
            for(int y = 1;y <= n;y++){
                if(x == y)continue;
                ll s1 = 0,s2 = 0;
                for(int k = 1;k < i;k++){
                    s1 = (s1 + (g[x][y][k] * f[x][y][i-k]) % z + (h[x][y][k] * f[y][y][i-k]) % z) % z;
                    //h[x][y][i]的不合法方案数 
                    s2 = (s2 + (g[x][y][k] * f[x][x][i-k]) % z + (h[x][y][k] * f[y][x][i-k]) % z) % z;
                    //g[x][y][i]的不合法方案数 
                }
                h[x][y][i] = (f[x][y][i] - s1 + z) % z;
                g[x][y][i] = (f[x][x][i] - s2 + z) % z;//
            }
    } 
    scanf("%d",&q);
    for(int i = 1;i <= q;i++){
        int x,y,d;
        scanf("%d%d%d",&x,&y,&d);
        printf("%lld\n",h[x][y][d]);
    }
    
    return 0;
    
}