#2142. 「SHOI2017」相逢是问候

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cyand1317

题目描述

Informatik verbindet dich und mich.
信息将你我连结。

B 君希望以维护一个长度为 n 的数组,这个数组的下标为从 1 n 的正整数。

一共有 m 个操作,可以分为两种:

  • 0 \ l \ r :表示将第 l 个到第 r 个数 (a_l, a_{l+1}, \dots, a_r) 中的每一个数 a_i 替换为 c^{a_i} ,即 c a_i 次方,其中 c 是输入的一个常数,也就是执行赋值

    a_i \leftarrow c^{a_i}

  • 1 \ l \ r :求第 l 个到第 r 个数的和,也就是输出:

    \sum_{i = l}^r a_i

因为这个结果可能会很大,所以你只需要输出结果 \mathrel{\mathrm{mod}} p 的值即可。

输入格式

第一行有四个整数 n, m, p, c ,所有整数含义见问题描述。
接下来一行 n 个整数,表示 a 数组的初始值。
接下来 m 行,每行三个整数,其中第一个整数表示了操作的类型。

  • 如果是 0 的话,表示这是一个修改操作,操作的参数为 l, r
  • 如果是 1 的话,表示这是一个询问操作,操作的参数为 l, r

输出格式

对于每个询问操作,输出一行,包括一个整数表示答案 \mathrel{\mathrm{mod}} p 的值。

样例

样例输入 1

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

样例输出 1

0
3

样例输入 2

1 40 19910626 2
0
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1

样例输出 2

1
2
4
16
65536
11418102
18325590
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558

数据范围与提示

对于 0\% 的测试点,和样例一模一样;
对于另外 10\% 的测试点,没有修改;
对于另外 20\% 的测试点,每次修改操作只会修改一个位置(也就是 l = r ),并且每个位置至多被修改一次;
对于另外 10\% 的测试点, p = 2
对于另外 10\% 的测试点, p = 3
对于另外 10\% 的测试点, p = 4
对于另外 20\% 的测试点, n \leq 100, m \leq 100
对于 100\% 的测试点, 1 \leq n \leq 50000, 1 \leq m \leq 50000, 1 \leq p \leq 100000000, 0 < c < p, 0 \leq a_i < p

数据貌似出锅了呢 (#9, #11)…… 有了重制数据之后会第一时间传上来的ヘ(´ー`ヘ)
2017.6.27 更新数据至清华算协 Git 中的版本
2017.7.14 修复数据,若仍有疑问请联系管理员 QuQ
2017.10 受 LOJ 删站事件影响,数据回复至错误版本
2017.11.29 再次修复数据并重测所有提交,若仍有疑问请联系管理员 QaQ