题目背景
这是一道 提交答案题。
题目描述
在 NOIP2044 的赛场上，小 D 遇到了这样一道题：
给出一个 n 个点的图，其中有 m 条带边权的有向边，有 q 个询问，每个询问形如从 u 号点走到 v 号点，长度为 w 的道路数量有多少？你只需要输出答案对 P 取模的结果即可。
小 D 思考了良久也不会做这道题，悻悻离场后，他从官网上取得了这道题的数据，共有 10 组数据。小 D 怎么也想做出来这道题，于是他开始寻求你的帮助，将 10 组数据的输入给了你。聪明的你一定可以帮小 D 计算出每组数据的输出的！
输入格式
输入文件 noip1.in~noip10.in 已经在下载文件中。
每个输入文件的第一行包括 4 个正整数 n,m,q,P，表示图中点数、边数、询问数目以及模数。点的编号为从 1 到 n 的整数。
接下来 m 行每行描述 m 条带权有向边，其中第 i 行包含 3 个整数 ai,bi,ci，表示第 i 条边的起点为 ai，终点为 bi，权值为 ci。
接下来 q 行描述询问，其中第 k 行包含 3 个整数 uk,vk,wk，表示第 k 个询问需要输出从 uk 号店走到 vk 号点，长度为 wk 的道路数量对 P 取模的结果。
输出格式
输出文件为 noip1.out~noip10.out，分别对应相应的输入文件。
每个输出文件中不超过 q 行，每行包含一个小于 P 的非负整数，表示该测试点前 q 个询问的答案。
输入输出样例
输入 #1复制
3 4 2 10 1 1 2 1 2 2 1 3 1 2 3 3 1 3 5 1 3 3
输出 #1复制
2 1
说明/提示
样例一解释：
对于第一组询问，一共有两条从 1 号点到 3 号点、长度为 5 的路径。假定边的编号从 1 到 4，则这两条路径经过的边为：
第 1 条：2→4
第 2 条：1→1→3。
有关其他样例
在测试数据下载中提供了每个测试点对应的sampleout，分别对应每个测试点第一个询问的正确输出
输入数据下载
下载链接
评分办法
暂无spj，按照 传统题 评分办法进行评测，只有你的答案与标准输出 完全相同 才能得到测试点的分数
提示
本题可能用到的知识：
特征多项式：对于 n×n 的矩阵 A，定义以 λ 为变量的 n 次多项式 f(λ)=det(λI−A)，其中 I 是 n 阶单位矩阵，det 是行列式。称 f(λ) 为 A 的特征多项式。
Cayley-Hamilton 定理：对于方阵 A 的特征多项式 f(λ)，一定有 f(A)=0。即将矩阵本身作为变量带入特征多项式，结果为零矩阵。
代码：
#include<bits/stdc++.h>
#define REG register
using namespace std;
inline void read(int& x){static char c;while(!isdigit(c=getchar()));x=c^48;while(isdigit(c=getchar()))x=(x*10)+(c^48);
} int n,m,q,p;inline int Pow(int a,int b,int p){int ans(1);while(b){if(b&1) ans=ans*a%p;a=a*a%p,b>>=1;}return ans;
}inline void exgcd(int a,int b,int& x,int& y){b?(exgcd(b,a%b,y,x),y-=a/b*x):(x=1,y=0);}int _InvX,_InvY;
int Inv(int a,int P){_InvY=_InvX=0;exgcd(a,P,_InvX,_InvY);return (_InvX%P+P)%P;
}const int P1=1<<12,P2=Pow(3,8,100005);int _2Mul[10005],_3Mul[10005];
int _2Sig[50005],_3Sig[50005];
int _2Phi[50005],_3Phi[50005];inline void Init(){_2Mul[0]=_3Mul[0]=1;for(REG int i=1;i<P1;++i) _2Mul[i]=_2Mul[i-1]*(i%2?i:1)%P1;for(REG int i=1;i<P2;++i) _3Mul[i]=_3Mul[i-1]*(i%3?i:1)%P2;_2Phi[0]=_3Phi[0]=1;for(REG int i=1;i<=50000;++i)_2Phi[i]=_2Phi[i/2]*_2Mul[i%P1]%P1*Pow(_2Mul[P1-1],i/P1,P1)%P1,_3Phi[i]=_3Phi[i/3]*_3Mul[i%P2]%P2*Pow(_3Mul[P2-1],i/P2,P2)%P2;_2Sig[0]=_3Sig[0]=0;for(REG int i=1;i<=50000;++i) _2Sig[i]=_2Sig[i/2]+i/2,_3Sig[i]=_3Sig[i/3]+i/3;
}inline int Binom(int n,int m){if(n<m) return 0;int Pw=_2Sig[n]-_2Sig[m]-_2Sig[n-m];int _2Ans,_3Ans;if(Pw>=12) _2Ans=0;else _2Ans=_2Phi[n]*Inv(_2Phi[m],P1)%P1*Inv(_2Phi[n-m],P1)%P1*Pow(2,Pw,P1)%P1;Pw=_3Sig[n]-_3Sig[m]-_3Sig[n-m];if(Pw>=8) _3Ans=0;else _3Ans=_3Phi[n]*Inv(_3Phi[m],P2)%P2*Inv(_3Phi[n-m],P2)%P2*Pow(3,Pw,P2)%P2;return (1ll*_2Ans*P2%p*Inv(P2,P1)%p+1ll*_3Ans*P1%p*Inv(P1,P2)%p)%p;
}inline void Work(){Init();read(n),read(m),read(q),read(p);for(REG int i=1;i<=m;++i){int u,v,w;read(u),read(v),read(w);}while(q--){int u,v,w;read(u),read(v),read(w);if(u==v){printf("%d\n",!w);continue;}if(!(v&1)) --w,--v;u|=1;if(w<0){puts("0");continue;}int Len=(v-u)>>1;printf("%d\n",Binom(Len,w));}
}int main(){Work();}
)