#1745. 术树数
术树数
术树数
题目描述
标题: 术树数 - Problem - QOJ.ac
The problem was used in the following contests:
小 W 拥有一个庞大的国家。这个国家初始的时候只有一座城池,编号为 1。小 W 打算记录他的国家交通发展的历程。具体的,小 W 记录了 Q 次操作,记每一次操作前编号最大的城市为 m,每次操作是如下三种操作中的某一种:
1 x v。小 W 占领了一座新的城市并将其编号为 m+1。在攻占完成后小 W 新建了一条连接 x 和 m+1 的权值为 v 的双向通行道路。(1≤x≤m,0≤v<V)2 x y v。小 W 新建了一条连接 x 和 y 的权值为 v 的双向通行道路。(1≤x≤m,0≤v<V)3 x y。小 W 询问连接 x 和 y 的所有路径的权值中,最小的那一条路径的权值。这里一条路径可以重复经过一条道路多次。(1≤x<y≤m)
在这里,小 W 定义一条路径的权值为路径上所有道路权值的 k 进制异或和。如果一条道路被经过了 x 次,则在计算异或和的时候也会计算 x 次。也就是说,有可能重复经过一条过路多次会使得路径权值变小。
注意城市 x、y 之间可能会出现很多条连接它们的道路,这些道路权值可能相同,也可能不同。
设 a 的 k 进制表示为 a1a2⋯am,b 的 k 进制表示为 b1b2⋯bn。,不妨在开头补零使得 m=n,则它们的 k 进制异或和的 k 进制表示为 (a1+b1)modk(a2+b2)modk⋯(an+bn)modk。
输入格式
第一行三个正整数,依次表示 Q,k,m。这里我们定义 V=km。
接下来 Q 行,每行若干个数字,表示一次操作。
输出格式
对于每一次操作 3,输出一行一个整数表示答案。
样例数据
样例输入
10 2 20
1 1 114514
1 2 191981
1 2 1926
1 2 817
3 1 4
3 1 5
2 3 5 1949
2 1 4 1001
3 1 4
3 1 5
样例输出
112852
113763
1001
1886
子任务
Subtask 1(2%):Q≤30,V≤2000。
Subtask 2(11%):Q≤1000,V≤100000。
Subtask 3(11%):不存在操作 2。
Subtask 4(19%):m=1。
Subtask 5(15%):k=2。
Subtask 6(3%):k 是奇数。
Subtask 7(39%):无特殊限制。
对于所有测试数据,满足 1≤Q≤2×105,2≤k,1≤m,V≤5×107。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
10 2 20
1 1 114514
1 2 191981
1 2 1926
1 2 817
3 1 4
3 1 5
2 3 5 1949
2 1 4 1001
3 1 4
3 1 5
112852
113763
1001
1886