BZOJ 4869 - [Shoi2017]相逢是问候

#数学 #数论 #数据结构 #线段树

Published on 2017-04-27

题目地址

描述

Informatik verbindet dich und mich.
信息将你我连结。

B 君希望以维护一个长度为 $n(n\le 50000)$ 的数组，这个数组的下标为从 $1$ 到 $n$ 的正整数。

一共有 $m(m\le 50000)$ 个操作，可以分为两种：

$0 \ l \ r$ ：表示将第 $l$ 个到第 $r$ 个数 $(a_l, a_{l+1}, \ldots, a_r)$ 中的每一个数 $a_i$ 替换为 $c^{a_i}$ ，即 $c$ 的 $a_i$ 次方，其中 $c$ 是输入的一个常数，也就是执行赋值
$a_i \leftarrow c^{a_i}$
$1 \ l \ r$ ：求第 $l$ 个到第 $r$ 个数的和，也就是输出：
$\sum_{i = l}^r a_i$

因为这个结果可能会很大，所以你只需要输出结果 $\mathrm{mod}\;p$ 的值即可。

分析

根据 BZOJ 2749 提供的信息， $n > 2$ 时， $\varphi(n)$ 是偶数，也就是说 $\varphi(n) \le \frac n 2$ 。则一个数 $n$ 经过 $O(\log n)$ 次 $n\leftarrow \varphi(n)$ 的变换就会变到 $n$ 。

再根据 UVa 10692 提供的信息可以知道，存在指数循环节公式

a^x\equiv a^{x \bmod \varphi(n) + \varphi(n)} \pmod n (x\ge \varphi(n))

一旦模数变为 $1$ ，意味着结果必然是 $0$ ，所以一个数经过至多 $O(\log n)$ 次修改操作就必然会变为一个常数。

于是我们得到一个算法，利用线段树维护区间和，同时维护一个区间的最小操作次数。设 $n$ 通过 $n\leftarrow\varphi(n)$ 的变换变到 $1$ 需要 $s$ 次，当执行修改操作的时候，如果当前区间的最小操作次数 $> s$ 时，则修改没有意义，直接不修改；否则正常递归下去。根据势能分析，我们用 $O(n\log^2 n)$ 的代价执行了 $O(n\log n)$ 次修改。

对于单点修改，使用与 UVa 10692 一模一样的方法即可，复杂度为 $O(\log^2 n)$ 。注意到本题中 $c$ 是一个定值，可以通过预处理的方法 $O(1)$ 求出 $c^x\bmod p(x\le 2^{32})$ 。具体做法是预处理 $\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)$ 。

总的复杂度： $O(n\log^2n + 65536 \cdot 16\log n)$ 。

一点后话：指数循环节公式只在 $x\ge \varphi(n)$ 时成立，在 UVa 10692 中，用试乘来判断是否 $\ge \varphi(n)$ ，我们在试乘的时候，是以上一层返回的取模后结果作为幂试乘，这样并不准确，应该使用上一层的答案进行试乘。但是放心，经过验证，这样做没有任何问题。因为如果 $x\ge \varphi(n)$ ，那么 $a^x\ge n$ 只在 $n = 6$ 时不成立，经过验证，这个带来的一系列后续影响不会造成答案的错误，所以大可放心使用。

代码

//  Created by Sengxian on 2017/04/26.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 4869 数论 + 线段树
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 50000 + 3, MAX_LOG_N = 40, LIM = 350000;

int calc(int n) {
    int res = n, t = n;
    for (int i = 2; i * i <= n; ++i) if (t % i == 0) {
        res /= i, res *= i - 1;
        while (t % i == 0) t /= i;
    }
    if (t > 1) res /= t, res *= t - 1;
    return res;
}

int pow1[MAX_LOG_N][1 << 16], pow2[MAX_LOG_N][1 << 16], cnt[MAX_LOG_N];
vector<int> mods;

inline int modPow(int b, int mod) {
    int idx = lower_bound(mods.begin(), mods.end(), mod) - mods.begin();
    if (b < cnt[idx]) return pow1[idx][b]; // < mod
    return ((ll)pow1[idx][b & 65535] * pow2[idx][b >> 16] % mod) + mod;
}

map<int, int> phi;
int n, m, p, c, a[MAX_N], s;

int calc(int a, int cnt, int mod) { // 如果答案 >= mod，返回 % mod + mod
    if (c == 1) return c % mod;
    if (cnt == 0) return a < mod ? a : a % mod + mod;
    int res = calc(a, cnt - 1, phi[mod]);
    return modPow(res, mod);
}

namespace SegmentTree {
    static const int MAX_NODE = (1 << 16) * 2;

    #define ls (((o) << 1) + 1)
    #define rs (((o) << 1) + 2)
    #define mid (((l) + (r)) >> 1)

    struct Node {
        int sum, minOperCnt;
    } nodes[MAX_NODE];

    int n, *a;

    inline Node merge(const Node &lhs, const Node &rhs) {
        Node res;
        res.sum = (lhs.sum + rhs.sum) % p;
        res.minOperCnt = min(lhs.minOperCnt, rhs.minOperCnt);
        return res;
    }

    void build(int o, int l, int r) {
        nodes[o].minOperCnt = 0;
        if (r - l == 1) nodes[o].sum = a[l];
        else {
            build(ls, l, mid), build(rs, mid, r);
            nodes[o] = merge(nodes[ls], nodes[rs]);
        }
    }

    void init(int _n, int *_a) {
        n = _n, a = _a;
        build(0, 0, n);
    }

    int query(int o, int l, int r, int a, int b) {
        if (r <= a || l >= b) return 0;
        if (l >= a && r <= b) return nodes[o].sum;
        return (query(ls, l, mid, a, b) + query(rs, mid, r, a, b)) % p;
    }

    void modify(int o, int l, int r, int a, int b) {
        if (r <= a || l >= b || nodes[o].minOperCnt > s) return;
        if (r - l == 1) nodes[o].sum = calc(SegmentTree::a[l], ++nodes[o].minOperCnt, p) % p;
        else {
            modify(ls, l, mid, a, b);
            modify(rs, mid, r, a, b);
            nodes[o] = merge(nodes[ls], nodes[rs]);
        }
    }

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

    void modify(int l, int r) {
        modify(0, 0, n, l, r);
    }

    void print() {
        for (int i = 0; i < n; ++i)
            cout << query(i, i + 1) << ' ';
        cout << endl;
    }
};

void prepare() {
    int now = p;
    while (now != 1) mods.push_back(now), now = phi[now] = calc(now);
    phi[1] = 1, mods.push_back(now);
    s = phi.size();

    reverse(mods.begin(), mods.end());
    for (int i = 0; i < (int)mods.size(); ++i) {
        pow1[i][0] = 1;
        for (int j = 1; j < (1 << 16); ++j)
            pow1[i][j] = (ll)pow1[i][j - 1] * c % mods[i];
        for (int j = 0; j < (1 << 16); ++j) {
            pow2[i][j] = pow1[i][j];
            for (int k = 0; k < 16; ++k) pow2[i][j] = (ll)pow2[i][j] * pow2[i][j] % mods[i];
        }
        if (c != 1) {
            ll tt = 1, t = 0;
            while (tt < mods[i]) tt *= c, ++t;
            cnt[i] = t;
        }
    }
}

int main() {
    n = readInt(), m = readInt(), p = readInt(), c = readInt();
    for (int i = 0; i < n; ++i) a[i] = readInt();

    prepare();
    SegmentTree::init(n, a);

    for (int i = 0; i < m; ++i) {
        int op = readInt(), l = readInt() - 1, r = readInt();
        if (op == 0) {
            SegmentTree::modify(l, r);
        } else printf("%d\n", SegmentTree::query(l, r));
    }

    return 0;
}

BZOJ 4872 - [Shoi2017]分手是祝愿 HDOJ 4630 - No Pain No Game

Sengxian's Blog

BZOJ 4869 - [Shoi2017]相逢是问候

描述

分析

代码