[CTSC2016]NOIP十合一

题目背景

这是一道 **提交答案题**。

题目描述

在 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$ 个整数 $a_i,b_i,c_i$,表示第 $i$ 条边的起点为 $a_i$,终点为 $b_i$,权值为 $c_i$。 接下来 $q$ 行描述询问,其中第 $k$ 行包含 $3$ 个整数 $u_k,v_k,w_k$,表示第 $k$ 个询问需要输出从 $u_k$ 号店走到 $v_k$ 号点,长度为 $w_k$ 的道路数量对 $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 \rightarrow 4$ 第 $2$ 条:$1 \rightarrow 1 \rightarrow 3$。 ### 有关其他样例 在测试数据下载中提供了每个测试点对应的sampleout,分别对应每个测试点第一个询问的正确输出 ### 输入数据下载 [下载链接](https://share.weiyun.com/5sk5wqh) ### 评分办法 暂无spj,按照 **传统题** 评分办法进行评测,只有你的答案与标准输出 **完全相同** 才能得到测试点的分数 ### 提示 本题可能用到的知识: **特征多项式**:对于 $n \times n$ 的矩阵 $A$,定义以 $\lambda$ 为变量的 $n$ 次多项式 $f(\lambda)=\det(\lambda I-A)$,其中 $I$ 是 $n$ 阶单位矩阵,$\det$ 是行列式。称 $f(\lambda)$ 为 $A$ 的特征多项式。 **Cayley-Hamilton 定理**:对于方阵 $A$ 的特征多项式 $f(\lambda)$,一定有 $f(A)=0$。即将矩阵本身作为变量带入特征多项式,结果为零矩阵。