LOJ2142 「SHOI2017」相逢是问候

Author Avatar
空気浮遊 2019年01月27日
  • 在其它设备中阅读本文章
  • 线段树
  • 扩展欧拉定理
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

一道跟 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 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • May 2025 1
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 31
    • August 2018 18
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 281
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material