#P5418. [CTSC2016] NOIP十合一(数据疑似有误)

    ID: 5131 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2016WC/CTSC/集训队提交答案O2优化

[CTSC2016] NOIP十合一(数据疑似有误)

题目背景

这是一道 提交答案题

题目描述

在 NOIP2044 的赛场上,小 D 遇到了这样一道题:

给出一个 nn 个点的图,其中有 mm 条带边权的有向边,有 qq 个询问,每个询问形如从 uu 号点走到 vv 号点,长度为 ww 的道路数量有多少?你只需要输出答案对 PP 取模的结果即可。

小 D 思考了良久也不会做这道题,悻悻离场后,他从官网上取得了这道题的数据,共有 1010 组数据。小 D 怎么也想做出来这道题,于是他开始寻求你的帮助,将 1010 组数据的输入给了你。聪明的你一定可以帮小 D 计算出每组数据的输出的!

输入格式

输入文件 noip1.in~noip10.in 已经在下载文件中。

每个输入文件的第一行包括 44 个正整数 n,m,q,Pn,m,q,P,表示图中点数、边数、询问数目以及模数。点的编号为从 11nn 的整数。

接下来 mm 行每行描述 mm 条带权有向边,其中第 ii 行包含 33 个整数 ai,bi,cia_i,b_i,c_i,表示第 ii 条边的起点为 aia_i,终点为 bib_i,权值为 cic_i

接下来 qq 行描述询问,其中第 kk 行包含 33 个整数 uk,vk,wku_k,v_k,w_k,表示第 kk 个询问需要输出从 uku_k 号店走到 vkv_k 号点,长度为 wkw_k 的道路数量对 PP 取模的结果。

输出格式

输出文件为 noip1.out~noip10.out,分别对应相应的输入文件。

每个输出文件中不超过 qq 行,每行包含一个小于 PP 的非负整数,表示该测试点前 qq 个询问的答案。

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

2
1

提示

样例一解释:

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

11 条:242 \rightarrow 4

22 条:1131 \rightarrow 1 \rightarrow 3

有关其他样例

在测试数据下载中提供了每个测试点对应的sampleout,分别对应每个测试点第一个询问的正确输出

输入数据下载

下载链接

评分办法

暂无spj,按照 传统题 评分办法进行评测,只有你的答案与标准输出 完全相同 才能得到测试点的分数

提示

本题可能用到的知识:

特征多项式:对于 n×nn \times n 的矩阵 AA,定义以 λ\lambda 为变量的 nn 次多项式 f(λ)=det(λIA)f(\lambda)=\det(\lambda I-A),其中 IInn 阶单位矩阵,det\det 是行列式。称 f(λ)f(\lambda)AA 的特征多项式。

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