TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5045
  • 题目
  • P5045「LibreOJ NOI Round #1」失控的未来交通工具
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 512m
    问题描述

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

    来源  LOJ 508