「SHOI 2017」相逢是问候【数论 + 线段树】

Time Limit: 40 Sec Memory Limit: 512 MB

Description

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

BB 君希望维护一个长度为 nn 的数组,这个数组的下标为从 11nn 的正整数。

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

  • 0 l r0 \ l \ r:表示将第 ll 个到第 rr 个数 (al,al+1,,ar)(a_l, a_{l+1}, \cdots, a_r) 中的每一个数 aia_i 替换为 caic^{a_i},即 ccaia_i 次方,其中 cc 是输入的一个常数,也就是执行赋值 aicaia_i \leftarrow c^{a_i}
  • 1 l r1 \ l \ r:求第 ll 个到第 rr 个数的和,也就是输出:i=lrai\displaystyle \sum_{i=l}^r a_i

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

Input

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

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

Output

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

Sample Input

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

Sample Output

1
2
0
3

Constraints

1n500001 \leqslant n \leqslant 50000, 1m500001 \leqslant m \leqslant 50000, 1p1081 \leqslant p \leqslant 10^8, 0<c<p0 < c <p, 0ai<p0 \leqslant a_i <p

Solution

欧拉定理的拓展:若 xφ(n)x \geqslant \varphi(n),则 cxcx mod φ(n)+φ(n) (mod n)c^x \equiv c^{x \text{ mod } \varphi(n) + \varphi(n)}\ (\text{mod }n)。易知一个数 nn 经过 O(logn)O(\log n)nφ(n)n \leftarrow \varphi(n) 的变换就会变到 11。在不断地套用欧拉定理时,指数模 φ(n)\varphi(n),指数的指数模 φ(φ(n))\varphi(\varphi(n)) \cdots 最多 O(logp)O(\log p) 次后就会变成模 1111,再操作就没有意义了。

考虑使用线段树维护区间和,同时维护一个区间的最小操作次数,不妨设 nn 通过 nφ(n)n \leftarrow \varphi(n) 的变换到 11 需要 ss 次。在执行修改操作时,如果当前区间的最小操作次数 >s>s,直接不修改;否则正常递归下去单点修改。

对于单点修改,可以通过预处理的方法 O(1)O(1) 求出 cn mod p (n232)c^n \text{ mod } p \ (n \leqslant 2^{32})。预处理 pow1(n)\text{pow}_1(n) 表示 cn mod pc^n \text{ mod } p 的值到 2162^{16};再处理 pow2(n)\text{pow}_2(n) 表示 cnc^n 平方 1414mod p\text{mod }p 的值到 2162^{16}cx mod pc^x \text{ mod }p 可以通过分段查表的方式快速算出:

1
pow1[b & 65535] * pow2[b >> 16] % p

总的时间复杂度为 O(nlog2n+65536×16logn)O(n \log^2n + 65536 \times 16 \log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

const int maxn = 50010, LOG_N = 27;
int n, m, p, c, a[maxn], mx[LOG_N], pow1[LOG_N][1 << 16], pow2[LOG_N][1 << 16];
vector<int> mods;
map<int, int> phi;
struct segment_tree {
int l, r, sum, cnt;
} tree[maxn << 2];

int calc_phi(int x) {
int res = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
res /= i, res *= i - 1;
while (x % i == 0) x /= i;
}
}
if (x > 1) res /= x, res *= x - 1;
return res;
}

int qp(int x, int mod) {
int pos = lower_bound(mods.begin(), mods.end(), mod) - mods.begin();
if (x < mx[pos]) return pow1[pos][x];
return 1LL * pow1[pos][x & 65535] * pow2[pos][x >> 16] % mod + mod;
}

int calc(int x, int cnt, int mod) {
if (c == 1) return c % mod;
if (cnt == 0) return x < mod ? x : x % mod + mod;
int res = calc(x, cnt - 1, phi[mod]);
return qp(res, mod);
}

void maintain(int k) {
tree[k].sum = (tree[k << 1].sum + tree[k << 1 | 1].sum) % p;
tree[k].cnt = min(tree[k << 1].cnt, tree[k << 1 | 1].cnt);
}

void build(int k, int l, int r) {
tree[k].l = l, tree[k].r = r;
if (l == r) {
tree[k].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
maintain(k);
}

void modify(int k, int l, int r) {
if (tree[k].cnt > mods.size()) {
return;
}
if (tree[k].l == tree[k].r) {
tree[k].sum = calc(a[l], ++tree[k].cnt, p) % p;
return;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
modify(k << 1, l, r);
} else if (mid < l) {
modify(k << 1 | 1, l, r);
} else {
modify(k << 1, l, mid), modify(k << 1 | 1, mid + 1, r);
}
maintain(k);
}

int query(int k, int l, int r) {
if (tree[k].l == l && tree[k].r == r) {
return tree[k].sum;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
return query(k << 1, l, r);
} else if (mid < l) {
return query(k << 1 | 1, l, r);
} else {
return (query(k << 1, l, mid) + query(k << 1 | 1, mid + 1, r)) % p;
}
}

int main() {
scanf("%d %d %d %d", &n, &m, &p, &c);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int cur = p; cur != 1; cur = phi[cur] = calc_phi(cur)) {
mods.push_back(cur);
}
phi[1] = 1, mods.push_back(1);
reverse(mods.begin(), mods.end());
for (int i = 0; i < mods.size(); i++) {
pow1[i][0] = pow2[i][0] = 1;
for (int j = 1; j < (1 << 16); j++) {
pow1[i][j] = pow2[i][j] = 1LL * pow1[i][j - 1] * c % mods[i];
for (int k = 0; k < 16; k++) {
pow2[i][j] = 1LL * pow2[i][j] * pow2[i][j] % mods[i];
}
}
if (c != 1) {
for (long long t = 1; t < mods[i]; t *= c) {
mx[i]++;
}
}
}
build(1, 1, n);
while (m--) {
int op, l, r;
scanf("%d %d %d", &op, &l, &r);
if (op == 0) {
modify(1, l, r);
} else {
printf("%d\n", query(1, l, r));
}
}
return 0;
}