#2989. 「CTSC2016」NOIP十合一

题目类型:答案提交 评测方式:Special Judge
上传者: YMDragon

题目描述

在 NOIP 2044 的赛场上,小 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 个询问的答案。

样例

样例输入

3 4 2 10
1 1 2
1 2 2
1 3 1
2 3 3
1 3 5
1 3 3

样例输出

2
1

样例说明

对于第一组询问,一共有两条从 1 号点到 3 号点、长度为 5 的路径。假定边的编号从 1 4 ,则这两条路径经过的边为:

  • 1 条: 2 \to 4
  • 2 条: 1 \to 1 \to 3

更多样例

我们给出了 noip1.sampleout~noip10.sampleout,分别对应每个测试点第一个询问的正确输出。

数据范围与提示

每个测试点单独评分。每个测试点你还可能获得部分分。

最终评测时,我们将根据你在每个数据中回答正确的询问个数进行计分。

如果你的输出不超过 q 行,且每行只包含一个不超过 P 的非负整数, 在最终评测时我们将认为你在第 i 行的输出是在回答对应测试点的第 i 个询问。

对于每个测试点,我们设置了 10 个评分参数 a_1, a_2, a_3, \ldots , a_9, a_{10} 。在你的方案中,若正确回答的询问个数为 w_{u} ,你的分数将为:若 w_u\ge a_i ,则该测试点获得 i 分,若多个 i 符合条件,取 i 最大的。

如果你的输出不符合格式要求,例如出现不小于 P 的整数或负数,输出超过了 q 行等,我们将不保证你能得到分数。

评分参数文件 noip.score 已在附加文件中。该文件共 10 行,第 i 行描述测试点 i 的评分参数。每行包含 10 个整数,依次表示 a_1, a_2, a_3, \ldots , a_9, a_{10}

提示

本题可能用到的知识:

特征多项式:对于 n\times n 的矩阵 A ,定义以 \lambda 为变量的 n 次多项式 f(\lambda) =\text{det}(\lambda I − A) ,其中 I n 阶单位矩阵, \text{det} 是行列式。称 f(\lambda) A 的特征多项式。

Cayley-Hamilton 定理:对于方阵 A 的特征多项式 f(\lambda) ,一定有 f(A) = 0 。即将矩阵本身作为变量代入特征多项式,结果为零矩阵。

编辑器加载中 …