BZOJ4869 相逢是问候

题面

维护长为 $N(N\leq 50000)$ 的数组,支持两个操作:

  1. $0\ \ l\ \ r$ 将$l$至$r$中的数$a_i$变为$c^{a_i}$,其中$c$为一个一开始给定的常数。
  2. $1\ \ l\ \ r$ 查询$l$到$r$中所有数的和。

操作数为$M(M\leq 50000)$。

输出全部 $\% p$,$p$为一个一开始就给定的常数($p\leq 10^8$)。

题解

又是一道和扩展欧拉定理有关的线段树题。

根据扩展欧拉定理:
扩展欧拉定理

那么如果设$d=c^x$

那么$c^{c^x}=c^d$,当$d>\varphi(p)$时:

$$\Large c^d=c^{d\%\varphi(p)+\varphi(p)}=c^{c^x\%\varphi(p)+\varphi(p)}$$

$$\huge =c^{c^{x\%\varphi(\varphi(p))+\varphi(\varphi(p))}+\varphi(p)}$$

经过自己手动将剩下的$\varphi(p)$一个个提出来之后发现会有很多$\varphi$套在一起。

然后注意到$p$变到$\varphi(p)$,$\varphi(\varphi(p))$,只要$\log p$次就会变成$1$。

当$\varphi^k(p)=1$时$c^{x\%\varphi}=0$,于是此时就不需要继续修改这个点了。

于是建一颗线段树,线段树每个节点维护两个值,一个是这个区间中数之和$sum$,另一个是区间中修改次数最少的数的个数$mn$。

当节点的$mn$的值$\geq p$变成$1$所需步数时不用修改当前节点,否则递归下去暴力修改。

但是这样的复杂度为$n\log^2n\cdot\log p$,无法通过此题,但是使用Sengxian的方法可以将$c^x\% \varphi^k(p)$优化到$O(1)$.

Sengxian的方法:
具体做法是预处理 $\mathrm{pow_1}(n)$ 表示 $c^n\bmod p$ 的值,处理到 $65536$;再预处理 $\mathrm{pow_2}(n)$ 表示 $c^n$ 平方 $16$ 次 $\mathrm{mod}\;p$ 的值,同样处理到 $65536$,则 $c^x\bmod p$ 可以通过分两段查表的方式快速算出:

pow1[b & 65535] * pow2[b >> 16] % mod

由于只有 $O(\log n)$ 个模数,对每个模数都预处理,那么复杂度为:$O(65536 \cdot 16\log n)$。

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define MAX_N 100007
#define ls (x << 1)
#define rs (x << 1 | 1)
#define __x % __y (__x - __x / __y * __y)
#define reg register
typedef long long ll;

int N, M, tot;
ll MOD, C, sum[MAX_N * 4], mn[MAX_N * 4], a[MAX_N];
ll pow1[50][1 << 16], pow2[50][1 << 16], cnt[50];
std::map<ll, int> phi, nums;

template <typename T> inline void read (reg T& x) {
    x = 0;
    reg char c = getchar();
    while (c < '0' || '9' < c) c = getchar();
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
}

inline ll quick_pow (reg ll x, reg ll p, reg ll mod) {
    if (C == 1) return mod <= 1 ? 0 : 1;
    reg ll ans = 1, tmp = 0;
    while (p) {
        if (p & 1) {
            ans = ans * x;
        }
        if (ans >= mod) ans = ans % mod, tmp = 1;
        p >>= 1;
        x = x * x;
        if (x >= mod) x = x % mod;
    }
    return ans + tmp * mod;
}

inline ll quick_quick_pow (reg ll x, reg ll mod) {
    reg int idx = nums[mod];
    if (x < cnt[idx]) return pow1[idx][x];
    return pow1[idx][x & 65535] * pow2[idx][x >> 16] % mod + mod;
}

inline ll calc (reg ll x, reg int cnt, reg ll mod) {
    if (mod == 0) return 0;
    if (C == 1) return C % mod;
    if (cnt == 0) return x < mod ? x : x % mod + mod;
    return quick_quick_pow(calc(x, cnt - 1, phi[mod]), mod);
}

inline ll calc (reg ll x) {
    reg ll ans = x, m = sqrt(x) + 1;
    for (reg ll i = 2;i <= m; ++i) 
        if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) ans = ans / x * (x - 1);
    return ans;
}

inline void init () {
    reg ll p = MOD, tmp, x;
    while (p > 1) {
        nums[p] = ++tot;
        tmp = calc(p);
        phi[p] = tmp;
        p = tmp;
    }
    nums[1] = ++tot;
    phi[1] = 0;
    p = MOD;
    for (reg int i = 1;i <= tot; ++i) {
        pow1[i][0] = 1;
        for (reg int j = 1, endd = (1 << 16); j < endd; ++j)
            pow1[i][j] = pow1[i][j - 1] * C % p;
        for (reg int j = 0, endd = (1 << 16); j < endd; ++j) {
            pow2[i][j] = pow1[i][j];
            for (reg int k = 0;k < 16; ++k)
                pow2[i][j] = pow2[i][j] * pow2[i][j] % p;
        }
        tmp = 0;
        x = 1;
        while (C != 1 && x < p) {
            x *= C, ++tmp;
        }
        cnt[i] = tmp;
        p = phi[p];
    }
}

inline ll min (ll a, ll b) {return a < b ? a : b;}

inline void update (reg int x) {
    sum[x] = sum[ls] + sum[rs];
    if (sum[x] > MOD) sum[x] = sum[x] % MOD;
    mn[x] = min(mn[ls], mn[rs]);
}

void build (reg int x, reg int l, reg int r) {
    if (l == r) {
        read(a[l]);
        sum[x] = a[l];
        return;
    }
    reg int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(x);
}

void modify (reg int x, reg int l, reg int r, reg int ql, reg int qr) {
    if (l > qr || r < ql) return;
    if (mn[x] >= tot) return;
    if (l == r) {
        sum[x] = calc(a[l], ++mn[x], MOD);
        return;
    }
    reg int mid = l + r >> 1;
    if (ql <= mid) modify(ls, l, mid, ql, qr);
    if (mid < qr) modify(rs, mid + 1, r, ql, qr);
    update(x);
}

ll query (reg int x, reg int l, reg int r, reg int ql, reg int qr) {
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[x];
    reg int mid = l + r >> 1;
    reg ll ans = 0;
    if (ql <= mid) ans = query(ls, l, mid, ql, qr) % MOD;
    if (mid < qr) ans = (ans + query(rs, mid + 1, r, ql, qr) % MOD) % MOD;
    return ans % MOD;
}

int main () {
    read(N), read(M);
    read(MOD), read(C);
    init();
    build(1, 1, N);
    reg int op, l, r;
    while (M--) {
        read(op);
        read(l);
        read(r);
        if (op == 0) { //modify
            modify(1, 1, N, l, r);
        } else { //query
            printf("%lld\n", query(1, 1, N, l, r) % MOD);
        }
    }
    return 0;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注