QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 1024 MB Total points: 100
[+2]

# 16. 玄学

Statistics

巨酱有 n 副耳机,他把它们摆成了一列,并且由 1 到n依次编号。每个耳机有一个玄学值,反映了各自的一些不可名状的独特性能。玄学值都是 0m1 间的整数。在外界的作用下(包括但不限于换线、上放、更换电源为核电、让kAc叔叔给它们讲故事),这些耳机的玄学值会发生改变。特别地,巨酱观察发现,每种作用 o 对应了两个整数 aobo,在这种作用之后,玄学值原本为 x 的耳机,其玄学值恰会变成 (aox+bo)mod

巨酱对他手头耳机的表现并不满意,遗憾的是,最近他并不有钱,无法任性,不能赶紧买买买以满足自己。手头紧张的他准备拟定一个相对经济的方案,通过各种作用来改善他手头玩具的性能。具体地说,为了尽快完成方案的制订,巨酱希望自己能高效地完成以下工作:

  1. 巨酱想到了一种操作,能让耳机的玄学值由 x 变为 (ax + b) \bmod m,并且他计划对编号为 ij 的耳机执行这种操作。
  2. 巨酱想知道如果将(并且仅将)自己的第 i 个到第 j 个计划按顺序付诸行动,编号为 k 的耳机的玄学值将会变成多少。

出于著名算法竞赛选手的矜持,巨酱表示自己才不需要你的帮助。但是如果巨酱真的厌倦了自己的玩具,它们就会被50包邮出给主席。为了不让后者白白捡到便宜,你考虑再三还是决定出手。

输入格式

第 1 行只有一个整数,表示本组测试数据的特征。特征值为一个 0 \sim 31 的整数。我们把这个整数转换成一个五位的二进制数,最低位为第一位。

如果第一位为 1,代表数据进行了加密,否则数据没有进行加密。对于已加密的数据,你需要把第一种操作中的 i,j 以及第二种操作中的 i,j,k 与上一次询问操作得到的答案 \text{lastans} 进行异或操作来得到正确的操作信息。\text{lastans} 的初始值视为 0

如果第二位为 1,代表修改操作会出现 (0x+ b) \bmod mb 不为 0)的形式,否则一定不会出现这样的修改。

如果第三位为 1,代表修改操作会出现 (ax+ 0) \bmod ma 不为 0)的形式,否则一定不会出现这样的修改。

如果第四位为 1,代表修改操作会出现 (ax+b) \bmod ma,b 均不为 0)的形式,否则一定不会出现这样的修改。

如果第五位为 1,则我们保证给出的 m 是一个质数,否则不保证。

第 2 行两个整数 n, m

第 3 行有 n 个用空格隔开的整数a_1,a_2,\dots,a_n0 \leq a_i < m,表示第 i 副耳机原本的玄学值。

第 4 行一个整数 q,表示巨酱的操作总数。

接下来有 q 行,每行 4 个或 5 个整数,第一个整数 cmd 是 12,表示这个操作的种类。若 cmd 为 1,接下来还有 4 个整数 i,j,a,b,表示巨酱增加一条计划,把耳机 i \dots j 的玄学值应用变换 x \mapsto (ax + b) \bmod m (保证 0 \leq a, b < m)。若 cmd 为 2,接下来还有 3 个整数 i,j,k,表示巨酱询问如果自己只作用变换 i \dots j,编号为 k 的耳机玄学值最终会变成多少。保证两种操作的 i,j 在解密后(如果数据是加密的)有 i \leq j

输出格式

对每个第 2 类操作,输出独占一行的一个整数,表示那次询问的结果。

样例一

input

24
3 5
1 2 3
5
1 1 2 3 2
1 2 3 4 3
2 1 1 3
1 1 3 1 4
2 1 3 2

output

3
4

样例二

input

7
3 5
1 2 3
5
1 1 2 0 3
1 2 3 4 0
2 1 1 3
1 2 0 2 0
2 2 0 1

output

3
4

样例三

见样例数据下载。

限制与约定

测试点编号 n 不超过 q 不超过 特征值
1 ~ 4 20 20 xxxxx
5 ~ 8 100000 100000 0001x
9 ~ 12 100000 100000 1110x
13 ~ 16 100000 100000 1111x
17 ~ 20 100000 100000 0010x
21 ~ 30 100000 100000 xxxxx
31 ~ 40 100000 600000 xxxxx

其中 x 为 0 和 1 中的任意数,特征值最左边为最高位。我们保证,同类型的测试点中加密与不加密的数据点各占 50%,且修改操作数不超过 100000,所有数的都可以用 int 存下。

由于本题数据量较大,请自行使用读入优化;由于测试点较多以及时限较长,为了大家的正常做题,请尽量减少提交本题的次数。