P3747 相逢是问候

大家好，欢迎来到IT知识分享网。

https://www.luogu.com.cn/problem/P3747

线段树+欧拉公式+预处理快速幂

由于 \(a^c \bmod p = a^{c\bmod \varphi (p)+\varphi(p)} \bmod p,(c>\varphi(p))\)

那么可以一层一层的迭代上去，由于 \(\varphi(p)\) 最多迭代 \(O(\log p)\) 次就会变成 \(1\)，此时在网上的指数就都是无用的了
所以用线段树维护这个数列，当修改时，如果某个区间内的所有数的指数层数都使得 \(p\) 被迭代为了 \(1\)，也就是所有层的指数都是 \(c\)，在加上最上面的一个 \(c^a\)（他的对应的 \(p\) 是 \(1\) 了，但由于 \(a\) 可能为 \(0\)，所以还要有一个 \(c\)，使得经过欧拉公式对指数的运算后结果为 \(1\)），那么再多更多的 \(c\) 也不会对答案产生影响了，就停止递归
如果没有，就递归下去暴力修改

这样，每个点最多被修改 \(O(\log p)\) 次，每次修改复杂度 \(O(\log p)\)，一共 \(n\) 个点，再加上线段树的复杂度，那么总复杂度 \(O(n\log n\log^2 p)\)
也就是和 此题 比较相近的思路，线段树上的操作每个都不会进行太多次，所以可以暴力进行

但如果这样做还是会T两个点，因为没有把快速幂的复杂度算进去
由于快速幂的模数数量不多，所以可以预处理所有 \(p^i\) 和 \(p^{10000i}\)，然后计算时合并即可

细节上，注意 mod 函数和取膜运算分别应该在什么时候使用

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN puts("")
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
	return y?x:-x;
}
#define N 50006
int n,m,c,p;
int phi[126],a[N];
void get_phi(int p,int id){
	phi[id]=p;
	phi[0]=id;
	if(p==1) return;
	int ret=p;
	for(reg long long i=2;i*i<=p;i++){
		if(!(p%i)) ret=ret/i*(i-1);
		while(!(p%i)) p/=i;
	}
	if(p>1) ret=ret/p*(p-1);
	get_phi(ret,id+1);
}
long long Pow[66][10006],Pow0000[66][10006];
inline long long mod(long long a,long long b){return a<b?a:(a%b+b);}
inline int power(long long a,long long b,long long Mod){
	long long ret=1;
	while(b){
		if(b&1) ret=mod(ret*a,Mod);
		a=mod(a*a,Mod);b>>=1;
	}
	return ret;
}
inline long long get_pow(long long b,long long id){
	return mod(Pow[id][b%10000]*Pow0000[id][b/10000],phi[id]);
}
struct Node{
	Node *ls,*rs;
	int num;
	int sum;
}dizhi[N*2],*root=&dizhi[0];
int tot;
inline void pushup(Node *tree){
	tree->sum=(tree->ls->sum+tree->rs->sum)%p;
	tree->num=std::min(tree->ls->num,tree->rs->num);
}
void build(Node *tree,int l,int r){
	if(l==r) return tree->num=1,tree->sum=a[l],void();
	tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
	int mid=(l+r)>>1;
	build(tree->ls,l,mid);build(tree->rs,mid+1,r);
	pushup(tree);
}
int ask(Node *tree,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree->sum;
	int mid=(l+r)>>1;
	int ret=0;
	if(ql<=mid) ret=(ret+ask(tree->ls,l,mid,ql,qr))%p;
	if(qr>mid) ret=(ret+ask(tree->rs,mid+1,r,ql,qr))%p;
	return ret;
}
int dfs(int now,int fi,int a,int p){
	if(p==1) return mod(now==fi?a:c,p);
	if(now==fi) return mod(a,p);
	return get_pow(dfs(now+1,fi,a,phi[now+1]),now);
}
void change(Node *tree,int l,int r,int ql,int qr){
	if(tree->num==phi[0]+1) return;
	if(l==r){
		tree->num++;
		tree->sum=dfs(1,tree->num,a[l],p)%p;
//			printf("l : %d  tree->sum : %d\n",l,tree->sum);
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) change(tree->ls,l,mid,ql,qr);
	if(qr>mid) change(tree->rs,mid+1,r,ql,qr);
	pushup(tree);
}
int main(){
	n=read();m=read();p=read();c=read();
	get_phi(p,1);
	for(reg int i=1;i<=phi[0];i++){
		for(reg int j=0;j<=10000;j++)
			Pow[i][j]=power(c,j,phi[i]),Pow0000[i][j]=power(c,j*10000,phi[i]);
	}
//		printf("phi[0] %d\n",phi[0]);
	for(reg int i=1;i<=n;i++) a[i]=read();
	build(root,1,n);
	reg int op,l,r;while(m--){
		op=read();l=read();r=read();
		if(op) printf("%d\n",ask(root,1,n,l,r));
		else change(root,1,n,l,r);
	}
	return 0;
}