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

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

题目描述

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

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

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

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

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

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

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


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

输入格式

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

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

输出格式

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

样例

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
0
1
1
6

sample1.png

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

数据范围与提示

对于 100%100\% 的数据,1n,q106,1<m109,1wm,0x,b<m,1c1091\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 中保证 uvu\neq v

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

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

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

Subtask # 分值 n,qn, q 的限制 mm 的限制 cc 的限制 附加限制
1 1111 1n,q1001 \leq n, q \leq 100 1<m1001 < m \leq 100 1c51 \leq c \leq 5
2 2121 1n,q2×1051 \leq n, q \leq 2\times 10^5 m=2m=2
3 1313 mm 是质数
4 77 mm 是奇数 图中任何时刻都不会出现简单环
5 1010
6 55 1c51 \leq c \leq 5 图中任何时刻不会有度数大于 22 的点
7 1313
8 2020 1n,q1061 \leq n, q \leq 10^6