可以发现， $$displaystyle c^{c^{c^cdots}}$$ 从下到上对应的模数是 (p,varphi(p),varphi(varphi(p)),varphi(varphi(varphi(p))),ldots ,1,1)。（为什么有两个 (1)？一会儿再说）
因此当一个数被修改了很多次以后它就不会再变了，维护一下一个数被修改了几次。
再来说为什么两个 (1)。以 (n=1,p=3,a_1=0,c=2) 为例：
[2^{2^0} mod 3=2,2^{2^{2^0}} mod 3=1
]
这是由于扩展欧拉定理得到的。也就是说，
[2^{2^{0 mod 1} mod 2} mod 3=2,
]
[2^{2^{2^{0 mod 1}mod 1 + 1}mod 2}mod 3=1.
]
这就造成了在 (mod 1) 时的不同。如果只有一个 (1)，会造成上下等价。其实，这是一组非常特殊的数据。
懒得卡常了，以下代码仅能 A bzoj。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, p, c, phi[105], cnt, a[50005], opt, uu, vv;
bool isy;
struct SGT{
int sum[200005], tag[200005];
void build(int o, int l, int r){
if(l==r) sum[o] = a[l];
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(l<=mid) build(lson, l, mid);
if(mid<r) build(rson, mid+1, r);
sum[o] = (sum[lson] + sum[rson]) % p;
}
}
int ksm(int a, int b, int p){
int re=1;
while(b){
if(b&1){
if((ll)re*a>=p) isy = true;
re = ((ll)re * a) % p;
}
if(b!=1 && (ll)a*a>=p) isy = true;
a = ((ll)a * a) % p;
b >>= 1;
}
return re;
}
int changeOneEle(int x, int hmn){
int tmp=x;
if(tmp>phi[hmn]) tmp = tmp%phi[hmn] + phi[hmn];
for(int i=hmn-1; i>=0; i--){
isy = false;
tmp = ksm(c, tmp, phi[i]);
if(isy) tmp += phi[i];
}
return tmp%p;
}
void update(int o, int l, int r, int x, int y){
if(tag[o]>=cnt-1) return ;
if(l==r)
sum[o] = changeOneEle(a[l], ++tag[o]);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) update(lson, l, mid, x, y);
if(mid<y) update(rson, mid+1, r, x, y);
sum[o] = (sum[lson] + sum[rson]) % p;
tag[o] = min(tag[lson], tag[rson]);
}
}
int query(int o, int l, int r, int x, int y){
if(l>=x && r<=y) return sum[o];
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
int re=0;
if(x<=mid) re = (re + query(lson, l, mid, x, y)) % p;
if(mid<y) re = (re + query(rson, mid+1, r, x, y)) % p;
return re;
}
}
}sgt;
int getPhi(int x){
int re=x;
for(int i=2; i*i<=x; i++)
if(x%i==0){
re = re / i * (i - 1);
while(x%i==0) x /= i;
}
if(x>1) re = re / x * (x - 1);
return re;
}
void prePhi(){
phi[cnt++] = p;
while(phi[cnt-1]!=1){
phi[cnt] = getPhi(phi[cnt-1]);
cnt++;
}
phi[cnt++] = 1;
}
int main(){
cin>>n>>m>>p>>c;
for(int i=1; i<=n; i++)
scanf("%d", &a[i]);
sgt.build(1, 1, n);
prePhi();
while(m--){
scanf("%d %d %d", &opt, &uu, &vv);
if(opt==0) sgt.update(1, 1, n, uu, vv);
else printf("%d
", sgt.query(1, 1, n, uu, vv));
}
return 0;
}
我们发现快速幂挺费时间的，那就把它搞掉。参考
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, p, c, phi[105], cnt, a[50005], opt, uu, vv, ccc[75][10005], ttt[75][10005];
bool isy, fcc[75][10005], ftt[75][10005];
struct SGT{
int sum[200005], tag[200005];
void build(int o, int l, int r){
if(l==r) sum[o] = a[l];
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(l<=mid) build(lson, l, mid);
if(mid<r) build(rson, mid+1, r);
sum[o] = (sum[lson] + sum[rson]) % p;
}
}
int ksm(int b, int x){
ll tmp=(ll)ttt[x][b/10000]*ccc[x][b%10000];
if(tmp>=phi[x])tmp = tmp % phi[x] + phi[x];
return tmp;
}
int changeOneEle(int x, int hmn){
int tmp=x;
if(tmp>phi[hmn]) tmp = tmp%phi[hmn] + phi[hmn];
for(int i=hmn-1; i>=0; i--){
isy = false;
tmp = ksm(tmp, i);
}
return tmp%p;
}
void update(int o, int l, int r, int x, int y){
if(tag[o]>=cnt-1) return ;
if(l==r)
sum[o] = changeOneEle(a[l], ++tag[o]);
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(x<=mid) update(lson, l, mid, x, y);
if(mid<y) update(rson, mid+1, r, x, y);
sum[o] = (sum[lson] + sum[rson]) % p;
tag[o] = min(tag[lson], tag[rson]);
}
}
int query(int o, int l, int r, int x, int y){
if(l>=x && r<=y) return sum[o];
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
int re=0;
if(x<=mid) re = (re + query(lson, l, mid, x, y)) % p;
if(mid<y) re = (re + query(rson, mid+1, r, x, y)) % p;
return re;
}
}
}sgt;
int getPhi(int x){
int re=x;
for(int i=2; i*i<=x; i++)
if(x%i==0){
re = re / i * (i - 1);
while(x%i==0) x /= i;
}
if(x>1) re = re / x * (x - 1);
return re;
}
void prePhi(){
phi[cnt++] = p;
while(phi[cnt-1]!=1){
phi[cnt] = getPhi(phi[cnt-1]);
cnt++;
}
phi[cnt++] = 1;
}
void preKsm(int x){
ccc[x][0] = 1>=phi[x]?1%phi[x]+phi[x]:1;
for(int i=1; i<=10000; i++){
ccc[x][i] = ((ll)ccc[x][i-1] * c)>=phi[x]?((ll)ccc[x][i-1] * c)%phi[x]+phi[x]:((ll)ccc[x][i-1] * c);
}
ttt[x][0] = 1>=phi[x]?1%phi[x]+phi[x]:1;
int tmp=ccc[x][10000]>=phi[x]?ccc[x][10000]%phi[x]+phi[x]:ccc[x][10000];
for(int i=1; i<=10000; i++)
ttt[x][i] = ((ll)ttt[x][i-1] * tmp)>=phi[x]?((ll)ttt[x][i-1] * tmp)%phi[x]+phi[x]:((ll)ttt[x][i-1] * tmp);
}
int main(){
cin>>n>>m>>p>>c;
for(int i=1; i<=n; i++)
scanf("%d", &a[i]);
sgt.build(1, 1, n);
prePhi();
for(int i=0; i<cnt; i++)
preKsm(i);
while(m--){
scanf("%d %d %d", &opt, &uu, &vv);
if(opt==0) sgt.update(1, 1, n, uu, vv);
else printf("%d
", sgt.query(1, 1, n, uu, vv));
}
return 0;
}