一道跟 Nephren 长得很像的题目。

Solution

从这题可以瞅见这种限定次数的区间操作线段树题目的一般套路。

顺便 luogu 题解的扩展欧拉定理判的好像还有一点小瑕疵。可能用 nephren 那种操作（最坏情况下复杂度多一个 $\log$）会比较稳妥。

收货最大的是快速幂预处理少一个 $\log$ 的操作...

Code

// Code by ajcxsu
// Problem: greetings

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }

const int N=50010;
int qp[2][40][10000];
int qpow(int x, int y, int mo) {
    int ret=1;
    while(y) {
        if(y&1) ret=1ll*ret*x%mo;
        x=1ll*x*x%mo, y>>=1;
    }
    return ret;
}

typedef long long ll;
#define ls x<<1
#define rs x<<1|1
ll sum[N<<3];
int mi[N<<3], a[N];
int n, m, mo, c, tot, to2;
int phi[N], d[N];
int cpow(int y, int mo) {
    return 1ll*qp[0][mo][y%10000]*qp[1][mo][y/10000]%phi[mo];
}
int cac(int l, int r, int a) {
    if(l==r) return a%phi[l];
    int f=min(l+5, r);
    int last=(f==r?a:c), tot;
    for(int i=f-1;i>l;i--) {
        tot=last, last=1;
        while(tot--) {
            last*=c;
            if(last>=phi[l]) return cpow(cac(l+1, r, a)+phi[l+1], l);
        }
    }
    return cpow(last, l);
}
void build(int x, int l, int r) {
    if(l==r) { sum[x]=a[l]; return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    sum[x]=sum[ls]+sum[rs];
}
void updata(int x, int l, int r, int xl, int xr) {
    if(mi[x]>=tot) return;
    if(l==r) { sum[x]=cac(0, ++mi[x], a[l]); return; }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr);
    if(xr>mid) updata(rs, mid+1, r, xl, xr);
    sum[x]=sum[ls]+sum[rs], mi[x]=min(mi[ls], mi[rs]);
}
int query(int x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return sum[x]%mo;
    int mid=(l+r)>>1, ret=0;
    if(xl<=mid) ret+=query(ls, l, mid, xl, xr);
    if(xr>mid) ret+=query(rs, mid+1, r, xl, xr);
    return ret%mo;
}
int Phi(int x) {
    int ret=1;
    for(int i=2;i*i<=x;i++)
        if(x%i==0) {
            while(x%i==0) ret*=i, x/=i;
            ret/=i, ret*=(i-1);
        }
    if(x>1) ret*=x-1; return ret;
}


int main() {
    gn(n, m, mo, c);
    for(int i=1;i<=n;i++) gn(a[i]); build(1, 1, n);
    phi[0]=mo;
    do {
        ++tot, phi[tot]=Phi(phi[tot-1]);
    } while(phi[tot]>1);
    phi[++tot]=1;
    for(int i=0;i<=tot;i++) {
        qp[0][i][0]=qp[1][i][0]=1;
        qp[0][i][1]=c%phi[i], qp[1][i][1]=qpow(c, 10000, phi[i]);
        for(int j=2;j<10000;j++)
            qp[0][i][j]=1ll*qp[0][i][j-1]*qp[0][i][1]%phi[i],
            qp[1][i][j]=1ll*qp[1][i][j-1]*qp[1][i][1]%phi[i];
    }
    int a, b, c;
    while(m--) {
        gn(a, b, c);
        if(!a) updata(1, 1, n, b, c);
        else printf("%d\n", query(1, 1, n, b, c));
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-loj-2142.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆