标签：线段树，欧拉定理
题目
题目描述
Informatik verbindet dich und mich.
信息将你我连结。
B 君希望以维护一个长度为 n 的数组，这个数组的下标为从 1 到 n 的正整数。
一共有 m 个操作，可以分为两种：
-
\(0 l r\)表示将第 l 个到第 r 个数\(（ a_l,a{l+1},...a_r）\)中的每一个数 \(a_i\)替换为 \(c^{a_i}\)，即 c 的 \(a_i\)次方，其中 c 是输入的一个常数，也就是执行赋值\(a_i = c^{a_i}\)
-
1 l r 求第 l 个到第 r 个数的和，也就是输出：\(\sum_{i=l}^{r}a_i\)
因为这个结果可能会很大，所以你只需要输出结果 mod p 的值即可。
输入输出格式
输入格式
第一行有三个整数 n; m; p; c，所有整数含义见问题描述。
接下来一行 n 个整数，表示 a 数组的初始值。
接下来 m 行，每行三个整数，其中第一个整数表示了操作的类型。
如果是 0 的话，表示这是一个修改操作，操作的参数为 l; r。
如果是 1 的话，表示这是一个询问操作，操作的参数为 l; r。
输出格式
对于每个询问操作，输出一行，包括一个整数表示答案 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
说明
• 对于 0% 的测试点，和样例一模一样；
• 对于另外 10% 的测试点，没有修改；
• 对于另外 20% 的测试点，每次修改操作只会修改一个位置（也就是 l = r），并且每个位置至多被修改一次；
• 对于另外 10% 的测试点， p = 2；
• 对于另外 10% 的测试点， p = 3；
• 对于另外 10% 的测试点， p = 4；
• 对于另外 20% 的测试点， n ≤ 100; m ≤ 100；
• 对于 100% 的测试点， 1 ≤ n ≤ 50000; 1 ≤ m ≤ 50000; 1 ≤ p ≤ 100000000; 0 < c <p; 0 ≤ ai < p。
分析
前置技能：欧拉定理的扩展
\[当x>\phi (p) 时 c^x \equiv c^{x\%\varphi (p)+\varphi(p) }(\mod p)\]定理中的p可以不为质数
附上证明
然后发现一个结论
这个操作在进行log p次之后一定是个定值，之后便没有意义了
用线段树维护这个过程，如果当前区间所有节点都已经不再变化那么就不修改了
所以最坏情况下每个数会修改\(O(\log p)\)次，每次会修改\(\log n\)个节点
对于一个数的快速幂需要计算\(\log p\)次，时间复杂度就过大
所以我们需要考虑优化掉计算快速幂的那个\(\log\)
因为底数为确定的C，我们可以预处理\(C^x\)和\(t^x\)，t为\(C^{10000}\)，然后可以快速从两个表中进行查找
code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
const int maxn=5e4+6,splitnum=1e4;
int n,m,p,c,k,t;
int sum[maxn<<2],num[maxn<<2],tag[maxn<<2],a[maxn],f[maxn][100],cc[maxn][100],ex_c[maxn][100],pp[100];
inline ll qpow(int x,int y,int mod){
ll re=1;
while(y){
if(y&1)re=(re*x)%mod;
y>>=1,x=(1ll*x*x)%mod;
}
return re;
}
void pushup(int x){sum[x]=(sum[lson]+sum[rson])%p;tag[x]=tag[lson]+tag[rson];}
void build(int x,int l,int r){
if(l==r){sum[x]=a[l];num[x]=0;tag[x]=r-l+1;return;}
build(lson,l,mid);build(rson,mid+1,r);
pushup(x);
}
void modify(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr&&!tag[x])return;
if(l==r){
num[x]++;sum[x]=f[l][num[x]];
if(num[x]==k)tag[x]--;
return;
}
if(ql<=mid)modify(lson,l,mid,ql,qr);
if(qr>mid)modify(rson,mid+1,r,ql,qr);
pushup(x);
}
inline int query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sum[x];
ll re=0;
if(ql<=mid)re+=query(lson,l,mid,ql,qr);
if(qr>mid)re+=query(rson,mid+1,r,ql,qr);
return re%p;
}
inline int phi(int x){
int re=x,y=sqrt(x);
rep(i,2,y)
if(!(x%i)){while(!(x%i))x/=i;re=re/i*(i-1);}
if(x-1)re=re/x*(x-1);
return re;
}
inline int q_p(int x,int a,int num){
if(a<=splitnum)return cc[a][num];
return (1ll*ex_c[a/splitnum][num]*cc[a%splitnum][num])%pp[num];
}
inline int get_(int x,int num,int d){
if(!num)if(x>pp[d])return x%pp[d];else return x;
t=get_(x,num-1,d+1);
double q=log(1.0/x*pp[d+1])/log(1.0*c)-num+1;
if(q<=0)t+=pp[d+1];
return q_p(c,t,d);
}
void Pre(){
rep(i,0,splitnum)
rep(j,0,k){
cc[i][j]=qpow(c,i,pp[j]);
int g=qpow(c,splitnum,pp[j]);
ex_c[i][j]=qpow(g,i,pp[j]);
}
rep(i,1,n)
if(a[i]==0){
f[i][1]=1;
rep(j,2,k)f[i][j]=get_(1,j-1,0);
}else rep(j,1,k)f[i][j]=get_(a[i],j,0);
}
int main()
{
n=read(),m=read(),p=read(),c=read();
k=0;pp[0]=p;
while(pp[k]-1){k++;pp[k]=phi(pp[k-1]);}
k++;pp[k]=1;
rep(i,1,n)a[i]=read();
Pre();
build(1,1,n);
while(m--){
int opt=read(),l=read(),r=read();
if(opt==0)modify(1,1,n,l,r);
if(opt==1)printf("%d\n",query(1,1,n,l,r));
}
return 0;
}
