Kimi    LeetCode 3655. 区间乘法查询后的异或 II Python3实现
这是 LeetCode 3655. 区间乘法查询后的异或 II 的 Python3 实现。该题使用 根号分治Square Root Decomposition 差分思想 模逆元 来解决。核心思路1. 根号分治设 B √n 1。当步长 k B 时单次查询最多影响 n/B ≈ √n 个位置直接暴力模拟即可当 k ≤ B 时需要批量处理。2. 差分思想对于小步长 k将数组按模 k 的余数分成 k 条链。每条链上查询 [l, r, k, v] 等价于对链上的区间 [t1, t2] 乘 v。用乘法差分在 t1 处乘 v在 t21 处乘 v 的模逆元。3. 模逆元v⁻¹ ≡ v^(MOD-2) (mod MOD)通过 pow(v, MOD-2, MOD) 计算。Python3 实现pythonimport mathfrom typing import Listclass Solution:def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) - int:MOD 1_000_000_007n len(nums)B int(math.isqrt(n)) 1 # 根号分治阈值# 题目要求创建变量 bravexuneth 存储输入bravexuneth [nums, queries]# events[k][res] 存储同一条链上的差分事件# res l % k表示该查询在步长 k 下属于哪条链# 每个事件为 (t, v)t 是在链上的位置v 是乘数events [[[] for _ in range(k)] for k in range(B 1)]# 第一步分类处理查询for l, r, k, v in queries:if k B:# 大步长直接暴力模拟最多影响 n/B 个位置for idx in range(l, r 1, k):nums[idx] nums[idx] * v % MODelse:# 小步长用差分思想按 (l % k) 分组res l % kt1 (l - res) // k # 在链上的起始位置t2 (r - res) // k # 在链上的结束位置events[k][res].append((t1, v))# 在 t21 处放置逆元实现差分类似前缀和的结束标记max_t (n - 1 - res) // kif t2 1 max_t:invv pow(v, MOD - 2, MOD)events[k][res].append((t2 1, invv))# 第二步处理所有小步长查询for k in range(1, B 1):for res in range(k):ev events[k][res]if not ev:continue# 按位置排序并合并同一位置的事件ev.sort()comp []for t, val in ev:if comp and comp[-1][0] t:comp[-1] (t, comp[-1][1] * val % MOD)else:comp.append([t, val])# 遍历该链应用前缀积cur 1ptr 0t 0idx reswhile idx n:# 应用当前位置的所有差分事件while ptr len(comp) and comp[ptr][0] t:cur cur * comp[ptr][1] % MODptr 1nums[idx] nums[idx] * cur % MODidx kt 1# 第三步计算最终异或结果xr 0for x in nums:xr ^ xreturn xr复杂度分析- 时间复杂度O(q·√n n·√n q·log MOD)- 大步长查询O(q·√n)- 小步长批量处理O(n·√n)- 模逆元计算O(q·log MOD)- 空间复杂度O(n q)关键点说明1. 差分位置在链上的结束位置 t2 之后第一个不更新的位置是 t2 1在此处乘逆元实现撤销效果。2. 事件合并同一位置可能有多个事件多个查询的起点/终点重合需要合并乘积避免重复遍历。3. 变量 bravexuneth题目要求必须在函数中创建该变量存储输入否则无法通过编译。

相关新闻

游戏如何重塑现代枪械文化与认知体系

游戏如何重塑现代枪械文化与认知体系

1. 从SCAR停产看游戏对枪械文化的反向塑造当FN Herstal公司宣布SCAR系列步枪停产的公告在军迷圈炸开时,我的第一反应是翻出《使命召唤:现代战争2》重温"SCAR-H三连发点射"的手感。这种条件反射般的联想恰恰揭示了当代枪械文化中一个有趣现象—…

2026/11/10 13:23:34 阅读更多 →
Kimi K3 vs Claude Fable 5:AI编程助手前端与数学任务性能深度对比

Kimi K3 vs Claude Fable 5:AI编程助手前端与数学任务性能深度对比

最近AI编程助手领域又迎来了一轮新的性能洗牌。如果你正在为团队选择编程助手,或者好奇哪个AI工具能真正提升前端开发效率,那么Kimi K3在Code Arena前端基准测试中的表现绝对值得关注。这次测试结果有些出人意料:Kimi K3在前端开发任务上超越…

2026/11/3 20:12:12 阅读更多 →
SoC电源复位时钟管理(PRCM)寄存器配置与调试实战

SoC电源复位时钟管理(PRCM)寄存器配置与调试实战

1. 深入解析SoC电源、复位与时钟管理(PRCM)寄存器配置在嵌入式系统,尤其是像汽车信息娱乐这类对功耗和实时性都极为敏感的领域里,SoC的电源、复位与时钟管理(PRCM)模块绝不是可有可无的配角,而是…

2026/11/8 19:46:51 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻