RT，不知道为什么 WA 了，只有 $90$ 分 /kk

我也看了这个，但还是没调出来 /kk

代码：

#include <stdio.h>

typedef long long ll;

typedef struct {
	ll val;
	bool flag;
} Node;

int a[50007], root[50007], phi[27], depth[50007];
ll tree[50007], b[50007][27];

inline Node new_node(ll val, bool flag){
	Node ans;
	ans.val = val;
	ans.flag = flag;
	return ans;
}

inline int euler(int n){
	int ans = n;
	for (register int i = 2; i * i <= n; i++){
		if (n % i == 0){
			ans -= ans / i;
			while (n % i == 0){
				n /= i;
			}
		}
	}
	if (n > 1) ans -= ans / n;
	return ans;
}

inline Node quick_pow(ll x, ll p, ll mod){
	Node ans;
	ans.val = 1;
	ans.flag = false;
	while (p){
		if (p & 1){
			ans.val *= x;
			if (ans.val >= mod){
				ans.val %= mod;
				ans.flag = true;
			}
		}
		x *= x;
		if (x >= mod){
			x %= mod;
			ans.flag = true;
		}
		p >>= 1;
	}
	return ans;
}

Node power_tower(int c, int a, int n, int index){
	if (phi[index] == 1) return new_node(0, true);
	if (n == 0) return new_node(a % phi[index], a >= phi[index]);
	int next_index = index + 1;
	Node x = power_tower(c, a, n - 1, next_index);
	if (x.flag) x.val += phi[next_index];
	return quick_pow(c, x.val, phi[index]);
}

int get_root(int k){
	if (root[k] == k) return k;
	return root[k] = get_root(root[k]);
}

inline void merge(int x, int y){
	int x_root = get_root(x), y_root = get_root(y);
	if (x_root != y_root) root[x_root] = y_root;
}

inline int lowbit(int x){
	return x & (-x);
}

inline void update(int n, int x, ll k, int mod){
	while (x <= n){
		tree[x] = (tree[x] + k) % mod;
		x += lowbit(x);
	}
}

inline ll get_sum(int x, int mod){
	ll ans = 0;
	while (x > 0){
		ans = (ans + tree[x]) % mod;
		x -= lowbit(x);
	}
	return ans;
}

int main(){
	int n, m, p, c, cnt = 0;
	scanf("%d %d %d %d", &n, &m, &p, &c);
	for (register int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		update(n, i, a[i], p);
	}
	for (register int i = 1; i <= n; i++){
		root[i] = i;
	}
	for (register int i = p; i != 1; i = euler(i)){
		phi[cnt++] = i;
	}
	phi[cnt] = 1;
	for (register int i = 1; i <= n; i++){
		for (register int j = 0; j <= cnt; j++){
			b[i][j] = power_tower(c, a[i], j, 0).val % p;
			if (j >= 2 && b[i][j - 2] == b[i][j] && b[i][j - 1] == b[i][j]){
				for (register int k = j + 1; k <= cnt; k++){
					b[i][k] = b[i][j];
				}
				break;
			}
		}
	}
	for (register int i = 1; i <= m; i++){
		int opt, l, r;
		scanf("%d %d %d", &opt, &l, &r);
		if (opt == 0){
			for (register int j = l; j <= r; j = get_root(j) + 1){
				if (depth[j] == cnt){
					merge(j - 1, j);
				} else {
					update(n, j, b[j][depth[j] + 1] - b[j][depth[j]], p);
					depth[j]++;
				}
			}
		} else {
			printf("%lld\n", ((get_sum(r, p) - get_sum(l - 1, p)) % p + p) % p);
		}
	}
	return 0;
}