快速幂 · 相关章节

位运算是 CSP-S 复赛里性价比最高的工具之一：状态压缩 DP、树状数组、哈希去重、快速幂、图形/棋盘类题目都依赖它。本章先把"数值在机器里怎么存"（原/反/补/移码）讲清楚，再系统整理位运算的语法、技巧与真题模型。每个知识点都配可编译的 C++17 示例。

倍增法(Binary Lifting)是一种基于"成倍增长"思想的高效算法，通过预处理将问题分解为多个$$2$$的幂次规模的子问题，从而在查询时实现快速合并求解。该算法在时间复杂度上通常能将线性查询优化为对数级，广泛应用于数论（快速幂）、图论（树上倍增求祖先/LCA）、RMQ（ST 表）等领域。

GESP 八级编程题（每场 2 道，每道 25 分，共 50 分）是拉开差距的关键。把近几届真题摊开看——202403 接竹竿、202406 空间跳跃·最远点对、202412 排队·树上移动、202509 最小生成树·最短距离、202603 子图最短路——反复考查的算法其实就这 10 个模板。