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

内存限制：512 MB 时间限制：1.200 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

最近，神犇在未来交通工具展览会上购买了一辆「$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$ 下车。

输出

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

样例输入 复制 

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

提示


数据范围：对于 $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 $ | $1 \leq c \leq 5 $ | 无 | | 3 | $13$ | $1 \leq n, q \leq 2\times 10^5$ | $m$ 是质数 | $1 \leq c \leq 5 $ | 无 | | 4 | $7$ | $1 \leq n, q \leq 2\times 10^5$ | $m$ 是奇数 | $1 \leq c \leq 5 $ | 图中任何时刻都不会出现简单环 | | 5 | $10$ | $1 \leq n, q \leq 2\times 10^5$ | $m$ 是奇数 | 无 | 无 | | 6 | $5$ | $1 \leq n, q \leq 2\times 10^5$ | 无 | $1 \leq c \leq 5 $ | 图中任何时刻不会有度数大于 $2$ 的点 | | 7 | $13$ | $1 \leq n, q \leq 2\times 10^5$ | 无 | $1 \leq c \leq 5 $ | 无 | | 8 | $20$ | $1 \leq n, q \leq 10^6 $ | 无 | 无 | 无 |

来源/分类

提交提交记录统计讨论版露一手!