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

P4681 [THUSC 2015] 平方运算 Solution

Description

给定序列 a = ( a 1 , a 2 , ⋯ , a n ) a=(a_1,a_2,\cdots,a_n) a=(a1,a2,,an) 和常数 p p p ,有 m m m 个操作,分以下两种:

  • modify ⁡ ( l , r ) \operatorname{modify}(l,r) modify(l,r):对每个 i ∈ [ l , r ] i \in [l,r] i[l,r] 执行 a i ← a i 2 m o d p a_i \leftarrow a_i^2 \bmod p aiai2modp.
  • query ⁡ ( l , r ) \operatorname{query}(l,r) query(l,r):求 ∑ i = l r a i \sum\limits_{i=l}^r a_i i=lrai.

Limitations

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

Solution

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

  • c y c l e cycle cycle:这个区间内的数是否全部进入循环节.
  • s u m i sum_i sumi:全部进入循环节的情况下,每个数平方 i i i 次后的和.
  • n o w now now:当前区间的和在循环节的第几个位置.
  • t a g tag tag:标记,表示儿子需要平方几次.

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

Code

4.27 KB , 9.45 s , 193.55 MB (in total, C++ 20 with O2) 4.27\text{KB},9.45\text{s},193.55\text{MB}\;\texttt{(in total, C++ 20 with O2)} 4.27KB,9.45s,193.55MB(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;
}

相关文章:

P4681 [THUSC 2015] 平方运算 Solution

Description 给定序列 a ( a 1 , a 2 , ⋯ , a n ) a(a_1,a_2,\cdots,a_n) a(a1​,a2​,⋯,an​) 和常数 p p p &#xff0c;有 m m m 个操作&#xff0c;分以下两种&#xff1a; modify ⁡ ( l , r ) \operatorname{modify}(l,r) modify(l,r)&#xff1a;对每个 i ∈ [ …...

【apt源】RK3588 平台ubuntu20.04更换apt源

RK3588芯片使用的是aarch64架构&#xff0c;因此在Ubuntu 20.04上更换apt源时需要使用针对aarch64架构的源地址。以下是针对RK3588芯片在Ubuntu 20.04上更换apt源到清华源的正确步骤&#xff1a; 步骤一&#xff1a;打开终端 在Ubuntu 20.04中&#xff0c;按下Ctrl Alt T打…...

Angular 2 表单深度解析

Angular 2 表单深度解析 引言 Angular 2作为现代前端开发的框架之一,以其灵活性和强大的功能赢得了众多开发者的青睐。在Angular 2中,表单处理是其中一个重要且复杂的部分。本文将深入解析Angular 2的表单,从基础知识到高级应用,旨在帮助开发者更好地理解和运用Angular 2…...

PHP 7 新特性

PHP 7 新特性 引言 PHP 作为一种广泛使用的服务器端脚本语言,自1995年诞生以来,已经经历了多个版本的迭代。PHP 7 是 PHP 的发展历程中的一个重要里程碑,它带来了许多新特性和改进,旨在提高性能、增强安全性和简化开发过程。本文将详细介绍 PHP 7 的新特性,帮助开发者更…...

vim如何解决‘’文件非法关闭后,遗留交换文件‘’的问题

过程描述&#xff1a; 由于我修改文件时&#xff08;一定得修改了文件&#xff0c;不做任何修改不会产生这个问题&#xff09;的非法关闭&#xff0c;比如直接关闭虚拟机&#xff0c;或者直接断开远程工具的远程连接&#xff0c;产生了以下遗留交换文件的问题&#xff1a; 点击…...

【练习】树形dp

G. Group Homework time limit per test: 3 s memory limit per test: 512 MB input: standard input output: standard output No, we don’t want group homework. It’s the place where KaTeX parse error: Expected EOF, got & at position 7: 1 1 &̲lt; 1 …...

Mybatis是如何进行分页的?

大家好&#xff0c;我是锋哥。今天分享关于【Mybatis是如何进行分页的&#xff1f;】面试题。希望对大家有帮助&#xff1b; Mybatis是如何进行分页的&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 MyBatis 实现分页的方式有很多种&#xff0c;最常见…...

【新春特辑】2025年春节技术展望:蛇年里的科技创新与趋势预测

&#x1f525;【新春特辑】2025年春节技术展望&#xff1a;蛇年里的科技创新与趋势预测 &#x1f4c5; 发布日期&#xff1a;2025年01月29日&#xff08;大年初一&#xff09; 在这个辞旧迎新的美好时刻&#xff0c;我们迎来了充满希望的2025年&#xff0c;也是十二生肖中的蛇…...

论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(五)

Understanding Diffusion Models: A Unified Perspective&#xff08;五&#xff09; 文章概括基于得分的生成模型&#xff08;Score-based Generative Models&#xff09; 文章概括 引用&#xff1a; article{luo2022understanding,title{Understanding diffusion models: A…...

C++并发:C++内存模型和原子操作

C11引入了新的线程感知内存模型。内存模型精确定义了基础构建单元应当如何被运转。 1 内存模型基础 内存模型牵涉两个方面&#xff1a;基本结构和并发。 基本结构关系到整个程序在内存中的布局。 1.1 对象和内存区域 C的数据包括&#xff1a; 内建基本类型&#xff1a;int&…...

JavaScript函数中this的指向

总结&#xff1a;谁调用我&#xff0c;我就指向谁&#xff08;es6箭头函数不算&#xff09; 一、ES6之前 每一个函数内部都有一个关键字是 this &#xff0c;可以直接使用 重点&#xff1a; 函数内部的 this 只和函数的调用方式有关系&#xff0c;和函数的定义方式没有关系 …...

【java学习笔记】@Autowired注解 使用方法和作用 | 配合@Component注解使用 | IOC控制反转

原本在类中&#xff0c;要用什么对象&#xff0c;就直接new一个对象。这种原始的方式 是由应用本身去控制实例的。 用了Autowired注解后&#xff0c;就相当于把实例&#xff08;对象&#xff09;的控制权 交给外部容器来统一管理&#xff08;降低耦合&#xff09;。&#xff08…...

数论问题76一一容斥原理

容斥原理是一种计数方法&#xff0c;用于计算多个集合的并集中元素的个数&#xff0c;以避免重复计算。以下是其基本内容及相关公式&#xff1a; 两个集合的容斥原理 若有集合A和集合B&#xff0c;那么A与B的并集中元素的个数等于A集合元素个数加上B集合元素个数&#xff0c;再…...

python-leetcode-从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣&#xff08;LeetCode&#xff09; # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right r…...

【Oracle篇】使用Hint对优化器的执行计划进行干预(含单表、多表、查询块、声明四大类Hint干预)

&#x1f4ab;《博主介绍》&#xff1a;✨又是一天没白过&#xff0c;我是奈斯&#xff0c;从事IT领域✨ &#x1f4ab;《擅长领域》&#xff1a;✌️擅长阿里云AnalyticDB for MySQL(分布式数据仓库)、Oracle、MySQL、Linux、prometheus监控&#xff1b;并对SQLserver、NoSQL(…...

设置jmeter外观颜色

设置jmeter外观颜色 方法&#xff1a; 步骤一、点击顶部选项 ->外观&#xff0c;这里提供了不同的主题&#xff0c;可选自己喜欢的风格。 步骤二、选择后&#xff0c;弹框提示点击Yes。...

计算机网络 IP 网络层 2 (重置版)

IP的简介&#xff1a; IP 地址是互联网协议地址&#xff08;Internet Protocol Address&#xff09;的简称&#xff0c;是分配给连接到互联网的设备的唯一标识符&#xff0c;用于在网络中定位和通信。 IP编制的历史阶段&#xff1a; 1&#xff0c;分类的IP地址&#xff1a; …...

神经网络和深度学习

应用 类型 为什么近几年飞速发展 数据增长&#xff0c;算力增长&#xff0c;算法革新 逻辑回归 向量化 浅层神经网络(Shallow neural network) 单条训练数据前向传播计算表达式 batch训练数据前向传播计算表达式 反向传播计算表达式 参数随机初始化 不能全部设为0 原因是同一…...

MySQL 基础学习(3):排序查询和条件查询

MySQL 查询与条件操作&#xff1a;详解与技巧 在本文中&#xff0c;我们将探讨 MySQL 中的查询操作及其相关功能&#xff0c;包括别名、去重、排序查询和条件查询等&#xff0c;并总结一些最佳实践和注意事项。 一、使用别名&#xff08;AS&#xff09; 在查询中&#xff0c…...

webAPI -DOM 相关知识点总结(非常细)

title: WebAPI语法 date: 2025-01-28 12:00:00 tags:- 前端 categories:- 前端WEB API 了解DOM的结构并掌握其基本的操作&#xff0c;体验 DOM 在开发中的作用 API简介 就是使用js来操作html和浏览器 什么是DOM? 就是一个文档对象模型&#xff0c;是用来呈现预计于任意htm…...

如何选择适合的单北斗变形监测一体机以提升基础设施安全?

本文将重点讨论如何选择适合的单北斗变形监测一体机&#xff0c;以增强基础设施的安全性。在当前基础设施建设快速发展的背景下&#xff0c;单北斗GNSS的应用显得尤为重要。通过深入理解单北斗变形监测的原理&#xff0c;用户能够更好地把握设备的核心优势&#xff0c;尤其是在…...

java自动带注释

...

Python多线程真能并行了吗?(GIL绕过技术全图谱:subprocess/numba/multiprocessing/cython/rustpy)

第一章&#xff1a;Python无锁GIL环境下的并发模型面试题汇总Python 的全局解释器锁&#xff08;GIL&#xff09;长期被视为多线程并发的瓶颈&#xff0c;但近年来随着 CPython 3.13 引入实验性无锁 GIL&#xff08;--without-pymalloc 配合 --with-per-object-gil 原型&#x…...

企业高效知识体系:8大核心特征+可落地搭建框架,告别知识散乱

对于企业而言&#xff0c;知识从来不是“文件堆”&#xff0c;而是能支撑业务、培养新人、规避风险的核心资产。很多企业陷入“文档满天飞、新人没人带、老员工离职带跑经验”的困境&#xff0c;本质是没有搭建起高效、完整的知识体系。今天就一次性讲透&#xff1a;一个能真正…...

Python实战:5分钟搞定小红书自动点赞脚本(附完整代码)

Python实战&#xff1a;5分钟实现小红书自动化互动工具开发指南 在当今内容爆炸的时代&#xff0c;社交媒体运营已成为个人品牌和商业推广的重要阵地。小红书作为国内领先的生活方式分享平台&#xff0c;其互动数据直接影响内容曝光和账号权重。对于开发者而言&#xff0c;掌握…...

PHP 8.5 升级生存指南:避免凌晨两点回滚的检查清单

定目标版本&#xff0c;定义内部支持策略在动 CI 或 Composer 之前&#xff0c;先回答一个问题&#xff1a;在你的组织里&#xff0c;这次升级"完成"意味着什么&#xff1f;确定目标和截止日期PHP 分支有两年的活跃支持&#xff0c;然后是两年的安全修复。官方支持表…...

80+经典游戏宽屏焕新:WidescreenFixesPack重塑怀旧体验

80经典游戏宽屏焕新&#xff1a;WidescreenFixesPack重塑怀旧体验 【免费下载链接】WidescreenFixesPack Plugins to make or improve widescreen resolutions support in games, add more features and fix bugs. 项目地址: https://gitcode.com/gh_mirrors/wi/WidescreenFi…...

车辆信号震动信号的滤波、幅值与能量分析——基于测试台采集文件ssjlbpp.m等的研究

车辆信号的震动信号的滤波、幅值以及能量分析&#xff0c;信号是利用测试台采集回来的 文件列表&#xff1a; ssjlbpp.m cxssjlbpp.m ssj.m fuzhissj.m翻了翻硬盘里压箱底的车辆测试台数据&#xff0c;哦对&#xff0c;还有那堆当时随手起的.mat之外的.m文件&#xff1a;ssjlbp…...

OpenClaw+GLM-4.7-Flash:个人网络安全监控助手

OpenClawGLM-4.7-Flash&#xff1a;个人网络安全监控助手 1. 为什么需要个人网络安全监控 去年我的开发机遭遇了一次恶意脚本攻击&#xff0c;导致本地Git仓库被篡改。事后排查发现&#xff0c;攻击者通过一个陈旧的SSH密钥漏洞入侵&#xff0c;而系统日志里其实早有异常登录…...

从FCN到U-Net:盘点深度学习图像分割中,那些‘放大’特征图的秘密武器与选型指南

从FCN到U-Net&#xff1a;解码图像分割中的特征图放大技术选型 在构建图像分割模型时&#xff0c;特征图的上采样操作往往是决定最终分割精度的关键环节之一。不同于分类任务只需输出一个类别标签&#xff0c;分割网络需要对每个像素进行分类&#xff0c;这就要求网络能够将低分…...