#508. 「LibreOJ NOI Round #1」失控的未来交通工具

内存限制:512 MiB 时间限制:1200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

最近,神犇在未来交通工具展览会上购买了一辆「 m 循环车」。这种交通工具的特点是:车门每行驶 m 米才能开启一次。

展会结束后他准备回家,然而插入钥匙后,车内的一切突然扭曲了起来 …… 接着他发现自己到了一个奇怪的地方。这时空中传来一个声音:

哈哈哈 …… 我请你们来这里,就是为了考验一下你们的水平。这个世界是一张无向图,有 n 个点,暂时还没有边。等一会我把边加上之后,每条边会有一个长度,第 i 条边长 w_i 米。
你们的车一旦驶上一条边,就必须开到这条边的尽头,中途没有回转的余地。

现在你们将要接受 q 次考验。考验有两种:

  1. 告诉你们三个整数 u,v,w 表示我在 u v 之间加了一条长 w 米的边;
  2. 告诉你们五个整数 u,v,x,b,c \ (u\neq v) ,其中 x,b 描述了一个伪随机数生成器,它第一次的返回值 f_1=x\bmod m ,以后每次的返回值 f_{i+1}=(f_i+b)\bmod m 。你们要回答,对于 i=1,2,\ldots,c ,有多少个 i 满足:如果你的车离最近一次能够开门的机会还有 f_i 米,那么存在一条路径使你能从 u 出发到 v 下车。

除非你们的回答全部正确且快速,否则我是不会放你们离开这里的 …… 哈哈哈 ……

按照套路,神犇自然是一眼秒掉了这个问题。不过为了不让黑恶势力白白出场,他想请你也解决一下这个问题。


简略题意:一个带边权无向图,有两种操作:加边以及询问在 x,x+b,...,x+(c-1)b 这些数中,有多少存在一条与之模 m 同余的从 u v 的路径(可以不是简单路径)。

输入格式

第一行三个整数 n,m,q
接下来 q 行,每行描述一次考验,内容如下:

  • \texttt{1 u v w} 表示 u v 之间加了一条长 w 米的边;
  • \texttt{2 u v x b c} 表示询问对于 i=1,2,\ldots,c ,有多少个 i 满足:如果你的车离最近一次能够开门的机会还有 f_i 米,那么存在一条路径使你能从 u 出发到 v 下车。

输出格式

对于每个第二种考验,输出一行一个整数表示答案。

样例

样例输入 1

6 6 10
1 1 2 3
2 1 2 0 0 1
1 2 3 3
1 1 3 3
2 1 2 0 0 1
1 4 5 6
1 5 6 4
2 4 6 2 0 1
1 3 4 6
2 1 6 0 1 6 

样例输出 1

0
1
1
6

样例解释 1

sample1.png

更多样例

见附加文件或备用网盘链接(提取码:a795

数据范围与提示

对于 100\% 的数据, 1\leq n,q\leq 10^6,1< m\leq 10^9,1\leq w\leq m,0\leq x,b< m,1\leq c\leq 10^9 操作 2 中保证 u\neq v

当车离最近一次能够开门的机会还有 r 米时,「存在一条路径使你能从 u 出发到 v 下车」的意思是 u v 之间存在一条路径(可以不是简单路径)长度模 m r

注意,路径可以不是简单路径。

出题人的关怀:由于输入规模较大,建议使用读入优化;请相信 LibreOJ 测评机的速度。

Subtask # 分值 n, q 的限制 m 的限制 c 的限制 附加限制
1 11 1 \leq n, q \leq 100 1 < m \leq 100 1 \leq c \leq 5
2 21 1 \leq n, q \leq 2\times 10^5 m=2
3 13 m 是质数
4 7 m 是奇数 图中任何时刻都不会出现简单环
5 10
6 5 1 \leq c \leq 5 图中任何时刻不会有度数大于 2 的点
7 13
8 20 1 \leq n, q \leq 10^6