当前位置：首页 > article >正文

P4681 [THUSC 2015] 平方运算 Solution

article 2025/1/30 15:54:02

Description

给定序列 $a=(a_1,a_2,\cdots,a_n)$ 和常数 $p$ ，有 $m$ 个操作，分以下两种：

$\operatorname{modify}(l,r)$ ：对每个 $\in [l,r]$ 执行 $a_i \leftarrow a_i^2 \bmod p$ .
$\operatorname{query}(l,r)$ ：求 $\sum\limits_{i=l}^r a_i$ .

Limitations

$\le n,m \le 10^5$
$\textcolor{red}{0} \le a_i < p$
$\in {\{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562,1034,5831,9905,9977\}}$
$2\text{s},250\text{MB}$

Solution

$\operatorname{modify}$ 操作不能直接标记，也不能直接暴力改.
但是模意义下的平方运算显然是有周期性的，打表发现，在 $p$ 取给定数时，所有数的周期的 $\operatorname{lcm}$ 不大于 $60$ ，并且每个数平方不超过 $11$ 次就会进入循环节.
考虑在线段树上维护：

$cyc l e$ ：这个区间内的数是否全部进入循环节.
$sum_i$ ：全部进入循环节的情况下，每个数平方 $i$ 次后的和.
$n o w$ ：当前区间的和在循环节的第几个位置.
$t a g$ ：标记，表示儿子需要平方几次.

特别地，如果没有全部进入循环节，则用 $sum_0$ 来记录和.
然后进入循环节的直接跳，没有的就暴力改（因为不超过 $11$ 次）.
注意当一个数进入循环节时，需要将 $sum_i$ 全部算出.
剩下就没什么了，一开始时把每个数平方的周期长度全算一遍即可.

Code

$4.27\text{KB},9.45\text{s},193.55\text{MB}\;\texttt{(in total, C++ 20 with O2)}$

// Problem: P4681 [THUSC 2015] 平方运算
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4681
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

struct Node {
    int l, r;
    bool cycle;
    int now, tag;
    array<i64, 60> sum;
};
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }

struct SegTree {
    vector<Node> tr;
    vector<int> P, vis;
    int M, mod;
    
    inline SegTree() {}
    inline SegTree(const vector<int>& a, int _mod):
                   P(_mod), vis(_mod, -1), M(1), mod(_mod) {
        for (int i = 0; i < mod; i++) get_loop(i);
        for (int i = 0; i < mod; i++)
            if (P[i] != 0) M = lcm(M, P[i]);
        
        const int n = a.size();
        tr.resize(n << 2);
        build(0, 0, n - 1, a);
    }
    
    inline void get_loop(int x) {
        for (int i = 0, y = x; ; i++, y = y * y % mod) {
            if (vis[y] != -1) {
                P[y] = i - vis[y];
                break;
            }
            else vis[y] = i;
        }
        for (int y = x; vis[y] != -1; y = y * y % mod) vis[y] = -1;
    }
    
    inline void upd(int u) {
        if (P[tr[u].sum[0]] != 0) {
			for (int i = 1; i < M; i++) 
			    tr[u].sum[i] = tr[u].sum[i - 1] * tr[u].sum[i - 1] % mod;
			tr[u].now = 0;
			tr[u].cycle = 1;
		}
		else tr[u].now = tr[u].cycle = 0;
    }
    
    inline void apply(int u, int k) {
        tr[u].tag = (tr[u].tag + k) % M;
        tr[u].now = (tr[u].now + k) % M;
    }
    
    inline void pushup(int u) {
        tr[u].cycle = tr[ls(u)].cycle && tr[rs(u)].cycle;
        tr[u].now = 0;
        if (!tr[u].cycle)
            tr[u].sum[0] = tr[ls(u)].sum[tr[ls(u)].now] + tr[rs(u)].sum[tr[rs(u)].now];
        else {
            int nowL = tr[ls(u)].now, nowR = tr[rs(u)].now;
            for (int i = 0; i < M; i++) {
                tr[u].sum[i] = tr[ls(u)].sum[nowL] + tr[rs(u)].sum[nowR];
                nowL = (nowL + 1) % M;
                nowR = (nowR + 1) % M;
            }
        }
    }
    
    inline void pushdown(int u) {
        if (tr[u].tag) {
            apply(ls(u), tr[u].tag);
            apply(rs(u), tr[u].tag);
            tr[u].tag = 0;
        }
    }
    
    inline void build(int u, int l, int r, const vector<int>& a) {
        tr[u].l = l;
        tr[u].r = r;
        if (l == r) {
            tr[u].sum[0] = a[l];
            tr[u].tag = 0;
            return upd(u);
        }
        const int mid = (l + r) >> 1;
        build(ls(u), l, mid, a);
        build(rs(u), mid + 1, r, a);
        pushup(u);
    }
    
    inline void square(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r && tr[u].cycle) return apply(u, 1);
        if (tr[u].l == tr[u].r) {
            tr[u].sum[0] = tr[u].sum[0] * tr[u].sum[0] % mod;
            return upd(u);
        }
        const int mid = (tr[u].l + tr[u].r) >> 1;
        pushdown(u);
        if (l <= mid) square(ls(u), l, r);
        if (r > mid) square(rs(u), l, r);
        pushup(u);
    }
    
    inline i64 query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum[tr[u].now];
        const int mid = (tr[u].l + tr[u].r) >> 1;
        i64 res = 0;
        pushdown(u);
        if (l <= mid) res += query(ls(u), l, r);
        if (r > mid) res += query(rs(u), l, r);
        return res;
    }
};

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m, p;
	scanf("%d %d %d", &n, &m, &p);
	vector<int> a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	SegTree seg(a, p);
	for (int i = 0, op, l, r; i < m; i++) {
	    scanf("%d %d %d", &op, &l, &r);
	    l--, r--;
	    if (op == 1) seg.square(0, l, r);
	    else printf("%lld\n", seg.query(0, l, r));
	}
	
	return 0;
}