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

P4681 [THUSC 2015] 平方运算 Solution

news 来源：原创 2025/5/14 19:43:03

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;
}

Description

Limitations

Solution

Code

相关文章：