题解：P3747 [六省联考 2017] 相逢是问候

· · 题解

前置知识

a^{b\bmod \varphi(p)+\varphi(p)} & b> \varphi(p) \\ a^b & b\le \varphi(p) \end{cases} \pmod p

特别地，当 \gcd(a,p)=1 的时候，可以直接对于指数用 \varphi(p) 取模。

递归 +\infty 次的幂塔，可以直接利用扩展欧拉定理按照公式那样子递归求解，一直到底层 p=1 的时候直接返回 0 即可。递归的时间复杂度为 O(\log p)，因为对于任意大于 1 的整数，\varphi(p) 为偶数。而对于偶数 p 的欧拉函数有 \varphi(p)\le \dfrac{p}{2}。

注意由于无穷幂塔是递归无线层的，所以肯定每一层的指数都肯定 >\varphi(p)，故直接取扩展欧拉定理的第二种情况即可。

int tower(int a,int n,int p){
    if(p==1) return 0;
    int t = phi(p);
    else return qpow(a,tower(a,t)+t,p);
}

本题

观察 a_i 的变化过程：a_i\to c^{a_i}\to c^{c^{a_i}}\dots \to c^{c^{c^{\dots^{a_i}}}}。

这是一个幂塔不断叠的过程，但是注意由于不是无限递归，所以其指数并不一定 >\varphi(p)，所以我们在递归求幂塔的时候我们不能像无穷幂塔那样子无脑直接取第二种情况了，因为会有情况 1 的出现。所以我们需要求出 c^{c^{c^{\dots^{a_i}}}} 的满足 \le p 前若干项，这样子可以在求幂的时候快速判断当前指数与 \varphi(p) 大小关系。

int tower(int i,int k,int id){
    if(id==lim) return 0;
    if(k==0) return a[i]%phi[id];
    if(C==1||(k-1<=up[i]&&p[k-1][i]<phi[id+1])) return qpow(tower(i,k-1,id+1),id);
    else return qpow(tower(i,k-1,id+1)+phi[id+1],id);
}

这是一个求幂塔的基本代码，其中 id 代表的是 p,\varphi(p),\dots 的一系列数的数组下标，其中 \varphi_{lim}=1，所以递归到 id 为 lim 的时候就是到了底层，这个时候 \bmod 1，直接返回 0 即可。同样指数为 0 的时候也可以直接返回 a_i 取模结果。否者我们将运用扩展欧拉定理，特判掉 c=1 的情况后，我们只需要判断后续的指数与 \varphi(v_{id}) 的大小关系即可，其中 v_{id} 是当前这一层的模数。

关于上一段中的后续指数的大小，也就是我之前说的需要对于每个 a_i 都预处理 c^{c^{c^{\dots^{a_i}}}} 的前若干项，如果后续项数超出了预处理的项数就代表一定超过了当前的 \varphi(v_{id})，否则拿之前预处理的结果和 \varphi(v_{id}) 比较即可。

其中 tower 函数中的 qpow 如果直接计算，会多一个 \log 的代价。这里需要用到光速幂，也就是如果直接计算 x^k 可以快速幂，但是如果我们想 O(1) 回答就可以使用 O(\sqrt k\log k) 预处理，O(1) 回答的光速幂，我们预处理 x^{0},x^1,\dots x^{B-1} 和 x^{B},x^{2B}\dots x^{B^2}，其中 B=\sqrt k。这样子 k=k\bmod B+\lfloor\dfrac{k}{B}\rfloor\times B，直接用预处理的两个信息相乘回答即可。

void init(){
    phi[lim=1]=P;
    while(phi[lim]>1) phi[lim+1]=getphi(phi[lim]),lim++;
    for(int i=1;i<=lim;i++){
        p1[i][0]=1;
        for(int j=1;j<=B;j++) p1[i][j]=1ll*p1[i][j-1]*C%phi[i];
        int z=p1[i][B]; p2[i][0]=1;
        for(int j=1;j*B<=2*P;j++) p2[i][j]=1ll*p2[i][j-1]*z%phi[i];
    }
    int z=0; c[z]=1; 
    while(c[z]<P&&z<=30) z++,c[z]=c[z-1]*C;
    z--;
    for(int i=1;i<=n;i++){
        p[up[i]=0][i]=a[i];
        while(up[i]<=z&&p[up[i]][i]<=z) p[up[i]+1][i]=p1[1][p[up[i]][i]],up[i]++;
    }
}

这是预处理的代码，一段是求出所有 p,\varphi(p),\varphi(\varphi(p))\dots，这些数的个数不超过 \log p 个。然后预处理光速幂。最后是处理 c^{c^{c^{\dots^{a_i}}}} 的前若干项。

有了以上的基础，我们已经会处理题目中的数论操作了，但是我们需要使用一个高效的结构来维护。

这里采用线段树，线段树可以轻松完成区间求和的任务。一般遇到区间修改，线段树都是把所要求的区间 [ql,qr] 分裂成 O(\log n) 个极大的节点区间进行整体修改，但是本题，可以发现我们无法维护进行一次幂塔操作之后区间所有数和的变化，只能递归到单点来暴力修改。还是需要上面的性质，幂塔只会递归 \log p 层，也就是说我们对于每个点的修改次数不超过 \log p 次，只需要暴力修改时间复杂度就是对的！所以我们对于每个线段树节点维护区间和，及其区间被操作次数最少的点的操作次数，只要哪个区间存在没有达到操作上界的点就暴力往这个区间中这些点的位置进行递归即可，每个叶子节点只会被保留修改 \log p 次。

时间复杂度 O(n(\log n\log p+\log^2p))。第一个 \log n\log p 是线段树操作所自带的 \log 复杂度和每个点被暴力递归到的次数。后面的 \log^2p 是每个点的操作次数乘以单次操作的时间复杂度（也就是求解幂塔的时间复杂度），其实我们可以通过提前处理 \rm tower 数组来把这个 \log^2p 变成 \log p，但是意义不大，因为一是这样子需要开 O(n\log^2p) 的空间，二是我们已经有了第一项 \log n\log p 的存在，即使这边去掉一个 \log 也避免不了复杂度为 2\log 的事实。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=4e5+10;
const int B=1e4;
const int maxlog=40;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int a[maxn],phi[maxn],p[maxlog][maxn],P,C,n; ll c[maxlog];
int up[maxn],p1[maxlog][maxn],p2[maxlog][maxn],lim,m;
int qpow(int k,int id){ return 1ll*p1[id][k%B]*p2[id][k/B]%phi[id]; }
int tower(int i,int k,int id){
    if(id==lim) return 0;
    if(k==0) return a[i]%phi[id];
    if(C==1||(k-1<=up[i]&&p[k-1][i]<phi[id+1])) return qpow(tower(i,k-1,id+1),id);
    else return qpow(tower(i,k-1,id+1)+phi[id+1],id);
}
struct SegmentTree{
    #define ls (p<<1)
    #define rs (p<<1|1)
    #define mid ((l+r)>>1)
    ll sum[maxn<<2]; int cnt[maxn<<2];
    void pushup(int p){ sum[p]=(sum[ls]+sum[rs])%P; cnt[p]=min(cnt[ls],cnt[rs]); }
    void build(int p,int l,int r){
        if(l==r){ sum[p]=a[l]; cnt[p]=0; return ; }
        build(ls,l,mid); build(rs,mid+1,r); pushup(p);
    }
    void modify(int p,int l,int r,int ql,int qr){
        if(cnt[p]>=lim) return ;
        if(l==r){
            sum[p]=tower(l,cnt[p]+1,1);
            cnt[p]++; return ;
        }
        if(ql<=mid) modify(ls,l,mid,ql,qr);
        if(qr>mid) modify(rs,mid+1,r,ql,qr);
        pushup(p);
    }
    ll query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return sum[p];
        if(qr<=mid) return query(ls,l,mid,ql,qr);
        if(ql>mid) return query(rs,mid+1,r,ql,qr);
        return (query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr))%P;
    }
}seg;
int getphi(int x){
    int res=x;
    for(int i=2;1ll*i*i<=x;i++){
        if(x%i) continue;
        res=1ll*res*(i-1)/i;
        while(x%i==0) x/=i;
    }
    if(x>1) res=1ll*res*(x-1)/x;
    return res;
}
void init(){
    phi[lim=1]=P;
    while(phi[lim]>1) phi[lim+1]=getphi(phi[lim]),lim++;
    for(int i=1;i<=lim;i++){
        p1[i][0]=1;
        for(int j=1;j<=B;j++) p1[i][j]=1ll*p1[i][j-1]*C%phi[i];
        int z=p1[i][B]; p2[i][0]=1;
        for(int j=1;j*B<=2*P;j++) p2[i][j]=1ll*p2[i][j-1]*z%phi[i];
    }
    int z=0; c[z]=1; 
    while(c[z]<P&&z<=30) z++,c[z]=c[z-1]*C;
    z--;
    for(int i=1;i<=n;i++){
        p[up[i]=0][i]=a[i];
        while(up[i]<=z&&p[up[i]][i]<=z) p[up[i]+1][i]=p1[1][p[up[i]][i]],up[i]++;
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>P>>C;
    for(int i=1;i<=n;i++) cin>>a[i];
    init(); seg.build(1,1,n);
    for(int i=1;i<=m;i++){
        int t,l,r; cin>>t>>l>>r;
        if(!t) seg.modify(1,1,n,l,r);
        else cout<<seg.query(1,1,n,l,r)<<"\n";
    }
    return 0;
}