← Real problems

etsr23r4p2

hardsegtreematheulerStatement on DMOJ

CP Lang

36 lines0.3 spec
// etsr23r4p2: "a[i] = base^a[i] on a range" and "sum on a range, mod p". A power tower settles
// modulo p after as many steps as the totient chain p, phi(p), ..., 1 is long, so each node keeps,
// for every number s of further raisings up to that length, the sum its range would have; a
// range raise shifts those sums along by one, and the shifts commute.
let (n, q, p, base) = read<(1..=50_000, 1..=50_000, 1..=100_000_000, 1..=100_000_000)>()
type Z = Mod<p>
domain I = 1..=n
let a = read<[I]Int>()
var moduli = [p]
while moduli.last! > 1:
    moduli.push(phi(moduli.last!))
domain Slot = 0..=moduli.len
// base^e modulo m, and whether the true power reaches m (generalized Euler needs the flag).
fn power(e: Int, big: Bool, m: Int) -> (big: Bool, val: Int):
    let exp = if big: e + m else: e
    var (val, reached, acc) = (1 % m, false, 1)
    for _ in 0..min(exp, 64):
        acc = min(acc * base, m)
        reached = reached or acc >= m
    (big: reached or (exp > 64 and base > 1), val: pow_mod(base, exp, m))
// x raised s times, modulo moduli[depth] (the last modulus once the chain runs out).
fn tower(s: Int, x: Int, depth: Int) -> (big: Bool, val: Int):
    let m = moduli[min(depth, moduli.len - 1)]
    if s == 0:
        return (big: x >= m, val: x % m)
    let below = tower(s - 1, x, depth + 1)
    power(below.val, below.big, m)
let sums = (x: [Slot]Z, y: [Slot]Z) => [Slot] s => x[s] + y[s]
let raise = Action.new(apply: (k: Int, x: [Slot]Z, len: Int) => [Slot] s => x[Slot.at(Int(s) + k) ?? Slot.last!], over: sums)
var st = SegTree(sums, [I] i => [Slot] s => Z(tower(Int(s), a[i], 0).val), act: raise)
for _ in 0..q:
    let (kind, l, r) = read<(0..=1, I, I)>()
    if kind == 0:
        st.apply(l..=r, 1)
    else:
        print(st.fold(l..=r)[Slot.first!])

Accepted C++

375 lines · 18.38 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

namespace IO {
const int BUFFER_SIZE = 1 << 16;

char input_buffer[BUFFER_SIZE];
size_t input_pos = 0, input_len = 0;

char output_buffer[BUFFER_SIZE];
int output_pos = 0;

char number_buffer[100];
uint8_t lookup[100];

void _update_input_buffer() {
    input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
    input_pos = 0;

    if (input_len == 0)
        input_buffer[0] = EOF;
}

inline char next_char(bool advance = true) {
    if (input_pos >= input_len)
        _update_input_buffer();

    return input_buffer[advance ? input_pos++ : input_pos];
}

template <typename T>
inline void read_int(T& number) {
    bool negative = false;
    number = 0;

    while (!isdigit(next_char(false)))
        if (next_char() == '-')
            negative = true;

    do {
        number = 10 * number + (next_char() - '0');
    } while (isdigit(next_char(false)));

    if (negative)
        number = -number;
}

template <typename T, typename... Args>
inline void read_int(T& number, Args&... args) {
    read_int(number);
    read_int(args...);
}

void _flush_output() {
    fwrite(output_buffer, sizeof(char), output_pos, stdout);
    output_pos = 0;
}

inline void write_char(char c) {
    if (output_pos == BUFFER_SIZE)
        _flush_output();

    output_buffer[output_pos++] = c;
}

template <typename T>
inline void write_int(T number, char after = '\0') {
    if (number < 0) {
        write_char('-');
        number = -number;
    }

    int length = 0;

    while (number >= 10) {
        uint8_t lookup_value = lookup[number % 100];
        number /= 100;
        number_buffer[length++] = char((lookup_value & 15) + '0');
        number_buffer[length++] = char((lookup_value >> 4) + '0');
    }

    if (number != 0 || length == 0)
        write_char(char(number + '0'));

    for (int i = length - 1; i >= 0; i--)
        write_char(number_buffer[i]);

    if (after)
        write_char(after);
}

void init() {
    // Make sure _flush_output() is called at the end of the program.
    bool exit_success = atexit(_flush_output) == 0;
    assert(exit_success);

    for (int i = 0; i < 100; i++)
        lookup[i] = uint8_t((i / 10 << 4) + i % 10);
}
}  // namespace IO

constexpr int maxa = 1e7 + 5, maxb = 11;

int c_phi(int x) {
    static int cache[maxa + 1] {};
    if (cache[x]) {
        return cache[x];
    }
    int& ans = cache[x];
    ans = x;
    for (int i = 2; i <= int(1e5); i++) {
        if (x % i != 0) {
            continue;
        }
        ans = ans / i * (i - 1);
        while (x % i == 0) {
            x /= i;
        }
    }
    if (x > 1) {
        ans = ans / x * (x - 1);
    }
    return ans;
}

pair<bool, int> bpow(long base, long exp, int mod) {
    bool of = false, base_of = false;
    long ans = 1;
    while (exp) {
        if (exp & 1) {
            of |= ans * base >= mod || base_of;
            ans = (ans * base) % mod;
        }
        base_of |= base * base >= mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return {of, ans};
}

struct SPow {
    static constexpr int logn = 24, low = 18;

    int base, mod, mexp;
    long lift[logn + 1], pcomp[1 << low];

    SPow(int base, int mod) : base(base), mod(mod) {
        {
            long x = 1;
            for (mexp = 0; x < mod; mexp++, x *= base)
                ;
        }
        pcomp[0] = 1;
        for (int i = 1; i < (1 << low); i++) {
            pcomp[i] = (pcomp[i - 1] * base) % mod;
        }
        lift[0] = base;
        for (int i = 1; i <= logn; i++) {
            lift[i] = (lift[i - 1] * lift[i - 1]) % mod;
        }
    }

    pair<bool, int> query(int exp) {
        if (mod == 1) {
            return {true, 0};
        }
        long ans = pcomp[exp & ((1 << low) - 1)];
        for (int i = logn; i >= low; i--) {
            if ((exp >> i) & 1) {
                ans = (ans * lift[i]) % mod;
            }
        }
        pair<bool, int> ans1 {exp >= mexp, ans};
        return ans1;
//        dbg(base, exp, mod, ans1.first, ans1.second);
//        assert(ans1 == bpow(base, exp, mod));
//        return bpow(base, exp, mod);
    }
};

int base;
vector<int> mphis;
vector<SPow> mpows;

pair<bool, int> cpow(int ind, int x, int mind) {
    if (!ind) {
        return {x >= mphis[mind], x % mphis[mind]};
    }
    int nmind = min(sz(mphis) - 1, mind + 1);
    auto [of, nx] = cpow(ind - 1, x, nmind);
    if (of) {
        nx += mphis[nmind];
    }
    dbg(nx);
    auto [cf, ans] = mpows[mind].query(nx);
    return {of || cf, ans};
}

int mod;

struct Node {
    array<int, maxb> v;

    Node operator+(const Node& r) {
        Node ans {};
        for (int i = 0; i < maxb; i++) {
            ans.v[i] = v[i] + r.v[i];
            if (ans.v[i] >= mod) {
                ans.v[i] -= mod;
            }
        }
        return ans;
    }

    Node shift(int ind) const {
        ind = min(ind, maxb);
        Node ans;
        auto ar = copy(v.begin() + ind, v.end(), ans.v.begin());
        fill(ar, ans.v.end(), v.back());
        return ans;
    }

    int operator()(int ind) const {
        return v[min(ind, maxb - 1)];
    }

    static Node c_from(int x) {
        Node ans;
        for (int i = 0; i < maxb; i++) {
            ans.v[i] = cpow(i, x, 0).second;
        }
        return ans;
    }
};

struct ST {
    int n;
    vector<Node> v, arr;
    vector<int> lazy;

    ST(const vector<Node>& arr) : n(sz(arr)), v(4 * n), arr(arr), lazy(4 * n) {
        build(1, 0, n - 1);
    }

    void build(int o, int l, int r) {
        if (l == r) {
            v[o] = arr[l];
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        v[o] = v[lc] + v[rc];
    }

    void update(int o, int l, int r, int ql, int qr, int x) {
        if (ql <= l && r <= qr) {
            v[o] = v[o].shift(x);
            lazy[o] += x;
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        }
        v[o] = (v[lc] + v[rc]).shift(lazy[o]);
    }

    void update(int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    int query(int o, int l, int r, int ql, int qr, int clazy) const {
        if (ql <= l && r <= qr) {
            return v[o](clazy);
        }
        clazy += lazy[o];
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            if (mid < qr) {
                return (query(lc, l, mid, ql, qr, clazy) +
                        query(rc, mid + 1, r, ql, qr, clazy)) %
                       mod;
            }
            return query(lc, l, mid, ql, qr, clazy);
        }
        return query(rc, mid + 1, r, ql, qr, clazy);
    }

    int query(int l, int r) const {
        return query(1, 0, n - 1, l, r, 0);
    }
};

void solve() {
    {
        SPow s(2, 1);
        dbg(s.query(0).second);
//        return;
    }
    int n, q;
    IO::read_int(n, q, mod, base);
    int arr[n];
    for (auto& a : arr) {
        IO::read_int(a);
    }
    {
        int x = mod;
        while (true) {
            mphis.push_back(x);
            if (x == 1) {
                break;
            }
            x = c_phi(x);
        }
        for (auto& a : mphis) {
            mpows.emplace_back(base, a);
        }
    }
    vector<Node> arr_v;
    for (auto& a : arr) {
        arr_v.push_back(Node::c_from(a));
    }
    ST arr_st(arr_v);
    while (q--) {
        int t, l, r;
        IO::read_int(t, l, r);
        l--;
        r--;
        if (t == 0) {
            arr_st.update(l, r, 1);
        } else {
            IO::write_int(arr_st.query(l, r), '\n');
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    IO::init();
    solve();
}