企业官网建设流程全解析

遇到过挺多人问这个组合的：快速幂和离散化，看起来是八竿子打不着的两个技巧，但很多题解偏偏把它们放一起讲。你可能也见过这种代码——前面一个函数叫pow_mod，后面一段排序去重再把原值映射成小编号，看得懂每行代码，但就是不太明白作者为什么要把它们凑一块。

我先给个直白的结论：它俩不是一类东西，但经常在同一道题里互为前提。

快速幂解决的是“指数特别大没法直接乘”的问题，复杂度从O(n)降到O(log n)；离散化解决的是“值域特别宽但数很少没法开数组”的问题，把稀疏的原始值压缩成密集的小编号，让桶、树状数组、线段树这类依赖连续下标的工具能用起来。很多涉及区间统计、计数、前缀和的题目，往往先离散化把数据“压扁”，再在某个步骤里用快速幂算方案数或组合数。你把这两个基本功练扎实了，其实顺手就把一大批中等偏上的题目的骨架给拿下了。

这篇文章我就按自己习惯的节奏来讲：先分别拆清楚两个技巧的本质，再给一套可以直接抄的模板，最后用一道组合场景的题把它们串起来，讲讲我在实际提交里踩过的那些坑——有的是错了好几次才想明白的，希望你能直接绕开。

1. 快速幂到底在优化什么：一个指数增长的故事

先从为什么要快速幂说起。假设你要算3^20，老老实实乘20次当然能算出来。但比赛里常见的不是20，而是10^9甚至10^18这种指数。循环乘一遍在时间上已经受不了，加上中途要取模，每次乘完还得缩小一下数字范围，腾挪的空间就更小了。

理解快速幂最简单的方式不是直接看代码，而是看指数在二进制下的展开。拿3^13举例，13的二进制是1101，也就是13 = 8 + 4 + 1。那么：

3^13 = 3^(8+4+1) = 3^8 * 3^4 * 3^1

原本的13次乘法，被拆成了3次乘法：先算3^1，再算3^4（连续平方两次），再算3^8（再平方）。每拆出一个二进制位，就多做一次“平方”操作，而当前位如果是1，就把对应的结果乘进答案里。所以整个过程，操作次数只和指数二进制下的位数有关——10^18也才60个bit，循环60次，比1000000000次不知道快到哪里去了。

配合取模运算的话，幂运算还有一个特别好的性质：

(a * b) % m = ((a % m) * (b % m)) % m

也就是说，每一步都能先取模再乘，把中间结果始终压在m这个量级，不会出现超大数。很多初学者卡在“取模规则”上，其实记住这一条就够了，因为平方、乘法都是同一套规律。

我平时写快速幂，基本就是下面的写法，用的是“降幂向右移位、底数持续平方”的思路：

typedef long long ll; ll fast_pow(ll base, ll exp, ll mod) { ll result = 1; base %= mod; while (exp > 0) { if (exp & 1) { result = (result * base) % mod; } base = (base * base) % mod; exp >>= 1; } return result; }

这里有个容易被忽略的点：base %= mod放在循环外面，是为了防止底数一开始就比模数还大，后面平方越界。result初始化成1而不是0，是因为指数为0时任何非零数的0次幂都等于1，这在排列组合、方案计数场景里非常关键，因为很多递推公式的初始状态就依赖这个“空集的方案数为1”的约定。

另外一个值得一提的细节是，很多递归版本写得挺好看，但比赛场景里我倾向于用迭代版本。原因很朴素：递归在极端情况会多压几层栈，取模运算多的时候反而容易出纰漏，迭代版的循环变量和底数都清清楚楚，调试时单步走一遍逻辑就全通了。

快速幂还有一种叫做“矩阵快速幂”的升级版，本质思路完全一样，只是把底数从数字换成了矩阵，乘法换成矩阵乘法。很多线性递推的题目，比如斐波那契数列的第n项，n大到10^18的时候，就能用矩阵快速幂搞定。不过矩阵快速幂的常数比较大，取模要记得每步都处理，不然矩阵里随便一个数都可能几十位。这篇文章后面不展开矩阵版本，先把基础版吃透更重要。

2. 离散化：把稀疏的坐标“压扁”成连续的小编号

离散化的感觉得先从一个具体场景说起。假设有10万个点，点的x坐标范围在0到10^9之间，你想统计每个x上有多少个点。第一反应是开一个10^9+1的数组，显然不可能——就算只存int，也要4GB内存，普通比赛环境直接爆了。

但换个角度看，坐标虽然很大，坐标的种类只有10万种。我们不需要为每一个整数坐标都留一个桶，只需要把出现过的10万个坐标映射到0..99999的编号上，问题就变成了一个普通的桶计数问题，内存开销瞬间从4GB降到400KB。

这个映射过程就叫离散化。核心步骤其实就三件事：排序 → 去重 → 二分定位。

我这边最常用的模板长这样：

vector<int> all; // 把用到的原始坐标全部塞进 all，可能有重复 sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); // 之后查询原始值 x 的“压缩编号” int id = lower_bound(all.begin(), all.end(), x) - all.begin();

排序是为了让值有先后顺序；unique配合erase去掉相邻重复元素，压缩后每个值只保留一份；lower_bound是二分查找第一个不小于x的位置，返回的迭代器减去起始位置，就是它在压缩序列中的下标。

这一步做完以后，原来的大值域就变成0到size-1的连续编号，树状数组、线段树、差分这些依赖“连续下标”的数据结构就能往上套了。

有人可能会问：既然都要排序了，为什么不能直接用unordered_map做映射，省掉二分的O(log n)？我实际用下来的经验是：unordered_map在数据量大、分布刁钻的场景里容易哈希冲突，常数极不稳定；另外，离散化之后我们经常要做“相邻编号之间的区间计算”，比如原始坐标间隔很大时，压缩后直接按编号做前缀和，如果用的是哈希表，这种连续的区间语义根本表达不了。所以标准做法就是排序去重加二分，稳定且可预测。

离散化有个常用细分变体，叫“坐标压缩”。它在处理图论、计算几何和模拟类问题的时候特别管用。比如一条数轴上有若干条线段，你需要知道哪些位置被覆盖了多少次。原始端点可能很稀疏，如果我们把所有的端点拿出来离散化，那么相邻两个离散点之间的区域，覆盖情况是完全一致的。这样就把“无限种坐标”压缩成了“端点之间的小区间”，每个区间当成一个点来处理，整个问题的规模就下来了。

我在处理这类覆盖问题时，还习惯把端点处理成“左闭右开”的区间：左端点入桶时加1，右端点出桶时减1。这样配合离散化，在扫描线上移动时不会出现边界叠加的混乱。坐标压缩这个变体的核心思想仍然是排序去重，只不过映射之后的“单位”从一个点变成了一个段，理解这一点对后面看复杂题解会轻松很多。

3. 两个技巧的联合作战：一个典型的计数问题框架

技术点分开讲都还好理解，但真正的价值在于怎么组合起来用。我随便构造一个场景（这类题在比赛里真的很多）：给出一组点，每个点有位置pos和权值val，权值种类最多10^5种，位置范围是0..10^9。你需要统计，按位置排序后，每个位置左侧所有点的权值乘积，对某个大质数取模。多个点位于同一位置时，权值要合并处理。

这个题你说它是快速幂还是离散化？其实都不是，而是两个都得用。

先把位置离散化——所有出现过的位置排序去重后获得编号。然后从前往后扫，每到一个编号就维护一个前缀乘积。因为乘积可能大得离谱，所以每一步都要取模；如果是快速幂场景，我们往往不是直接维护乘积，而是维护“每个权值出现了几次”，最后算总权值prod(val_i ^ cnt_i)。这里指数cnt_i可能很大，需要累加，快速幂就派上用场了——虽然在这个具体例子里单点更新和统计看起来像前缀积，但一旦涉及“多次乘同一个数再取模”或者“统计一个数的出现次数后再整体算贡献”，快速幂就是唯一合理的选择。

我把这个组合流程总结成一张操作表，方便你对号入座：

这类题目最典型的组合方式就是：先离散化拿到“编号域”，然后在编号域上做各种统计，最后用快速幂算带指数的贡献。你会发现，这两个技巧一旦熟练，很多看上去要求“数据结构+数论”的水题，其实底子就这么简单。

另外还有一类经典问题叫“区间内不同数字的个数”，它不一定需要快速幂，但离散化几乎必用：原始值域太大，直接把每个数字映射成小编号，然后用树状数组离线维护last_pos，扫一遍就出来了。这类题考察的是“离散化+数据结构”的组合，和前面那种“离散化+快速幂”是两条路，但离散化作为地基是一样的。

4. 代码模板与注意事项：把组合用法直接落地

光说不练是假把式，我直接给一套我本地验证过、比赛中也常拿来改的组合代码模板。场景就用第三节的例子：一堆点，按位置求前缀权值贡献。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007LL; ll fast_pow(ll base, ll exp, ll mod) { ll result = 1; base %= mod; while (exp) { if (exp & 1) result = (result * base) % mod; base = (base * base) % mod; exp >>= 1; } return result; } int main() { int n; cin >> n; vector<ll> pos(n), val(n); vector<ll> all; for (int i = 0; i < n; i++) { cin >> pos[i] >> val[i]; all.push_back(pos[i]); } // 离散化 sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int m = all.size(); vector<ll> cnt(m, 0); // 同一位置合并计算幂次 vector<ll> prod(m, 1); // 维护前缀贡献，初始为1 for (int i = 0; i < n; i++) { int id = lower_bound(all.begin(), all.end(), pos[i]) - all.begin(); cnt[id] = (cnt[id] + 1) % (MOD - 1); // 费马小定理优化见下文 prod[id] = (prod[id] * val[i]) % MOD; } // 其实这里prod维护的是乘积；如果要用频次，再对每个val[i]快速幂即可。 // 此处演示快速幂的使用场景： for (int i = 0; i < m; i++) { ll contribution = fast_pow(prod[i], cnt[i], MOD); // 根据题目要求累加/更新答案，这里只是一个示意 } return 0; }

这里有两个细节必须讲清楚，不然你直接抄代码会出问题。

第一，MOD - 1那个取模不是随便写的。在模数为素数p时，费马小定理告诉我们a^(p-1) ≡ 1 (mod p)，所以指数部分可以对p-1取模来缩小指数。这是很多计数题里的常见套路，属于快速幂的“配套优化”。但注意必须先确认模数是素数，如果不是素数，比如MOD = 1000000009（也是素数）一般没事，但如果是合数，就不能这么随便对指数降幂。我用MOD - 1纯粹是为了给指数做“降幂”，千万不要把模数和指数模混在一个变量里搞糊涂。

第二，prod[i]初始化为1而不是0，是因为乘法群里的单位元是1。如果你用0初始化，所有前缀乘积都变成0了，这在计数场景里是个特别容易翻车的小地方。

再分享几个提交时最容易踩的坑：

• 离散化后别忘了用映射后的编号去访问数组。我见过不少选手排序去重做得很好，结果统计时还用原来的大坐标直接当下标，数组越界后程序飘出各种奇怪结果。正确姿势是一定要在插入或查询时同步用lower_bound转成编号。
• 同一坐标多个点不要重复创建桶。之前踩过的坑是把所有点直接push进all，但没去重，导致桶的数量变多，编号和后续的区间处理对不上。去重这步真的是离散化的灵魂。
• 快速幂里base没取模。底数比模数大时，平方后会膨胀得很厉害；虽然最终取模前C++的long long可能还扛得住，但乘法过程中溢出就完蛋了。所以第一步base %= mod绝对不能省。
• 递归快速幂写顺手了容易忘记终止条件。我有次配了个“指数为0返回1”的条件，但写在exp判断之前，导致负数指数时死循环。后来统一用迭代版本，再也没碰上过这种脑残问题。

5. 从题目难度的角度重新看这两个基本功

如果你经常刷题，会注意到一个现象：快速幂和离散化很少单独考，它们更像是“前置技能”.

有些朋友可能觉得难，是因为把它们当成了“高级算法”来看。实际拆开看，快速幂就是“二进制拆指数+平方复用”，离散化就是“排序去重+二分映射”，两个都能在10分钟内讲清楚。卡住大家的大概率不是原理，而是“不知道什么时候用”。我提供一个比较实用的判断依据：

• 看到“第n项”“n很大”“指数/次幂”并且n到10^9以上，就该想快速幂。
• 看到“值域很大”“坐标数量很少”“需要开数组但开不下”，就该想离散化。
• 两个同时出现，比如“大范围坐标上的方案数/计数/幂贡献”，那就是组合套路的经典场景。

我自己的习惯是，拿到题先问一句：“数据范围里谁是瓶颈？”如果瓶颈在值域，就离散化；如果瓶颈在指数，就快速幂；如果两个都在，那就老老实实都做。很多选手一上来就纠结于“用什么高级数据结构”，反而把最简单的两个基本功给忘了。

还有一类变体值得提一嘴：离线处理与二分答案配合离散化。比如你需要判断某个阈值下覆盖区间数量是否满足条件，直接离散化所有可能出现的阈值再逐个验证，比在线查找快得多。这个思路在二维平面矩形覆盖计数里也见过——横纵坐标各离散化一次，得到网格点，再在网格上做前缀和。原来的大坐标系可能是1e9 * 1e9，离散化之后变成k * k的小网格，思路一旦转过弯来，代码实现其实非常直白。

6. 一段多日实测的心得：边界情况和调试方式

写这类组合题，最折磨人的不是主逻辑，而是边界情况。我总结了几个实战里反复让我翻车的点，按“坑的程度”排个序：

坑1：空数据集。当all为空，离散化之后m=0，代码里如果还有m-1这种下标访问，整段直接崩。比赛里一般会保证非空，但做单元测试或者自己造数据时，最好先判空再进主流程。

坑2：只有一种坐标的情况。所有点挤在一个位置，离散化后只有一个编号。此时所有统计都落在一个桶里，如果你写的是“相邻编号做差”的逻辑，循环范围得想清楚，别把i+1越界当成正负号问题查半天。

坑3：模数不是质数，却用了费马小定理降幂。指数降幂和乘法取模是两回事，如果模数不满足质数条件，cnt % (MOD-1)就是错的。遇到这种情况，老老实实直接快速幂算，别贪心降幂省那点常数。我见过有人在这上面WA了十几次，最后发现费马小定理只能用在质数模数。

坑4：pow_mod里参数类型不统一。底数用long long，指数用int，在数据量大时int会溢出成负数，然后位运算逻辑全乱。干脆全部用long long，一了百了。

除了边界，我还想推荐一个调试技巧：用阻力最小的方式对比验证。拿一个数据量极小的测试样例，不用快速幂、也不用离散化，用最直白的模拟方式算一遍答案，再跟你快速幂+离散化的结果对拍。对拍数据范围就控制在n<=10，值域却可以故意做得很大。这样能快速确认是映射错还是幂运算错。我到现在写任何带取模和离散化的题，都会先在本地用这个“土办法”跑一遍，再交去评测。

这不是什么高级技巧，但对排查“边界情况”特别有效。很多时候你以为是对拍代码有问题，其实是对手写爬虫爬出来的输出有问题——两边逻辑都不一致，对拍结果自然全是红的。遇到这种情况，先冷却十分钟，把两边的中间结果都打印出来，一步一步比对，往往很快就能定位到是“映射编号差1”还是“指数取模方向不对”。

7. 一个完整实例：从题意到AC的全过程

为了让你把前面所有内容串起来，我起了个小题目，把完整思考链路写出来。题目是这样的：

有n个物品，每个物品有一个位置pos_i（可重复）和一个类型type_i。现在问你，按位置从小到大排列后，每个位置左侧（含本位置）所有物品的类型乘积之和，对998244353取模是多少。这里“类型乘积”指的是把同类型物品的数量作为指数，对该类型进行幂运算后得到的权值。n<=2e5，pos_i和type_i都在0..1e9。

拿到这个题，我的第一反应就是：位置范围1e9但只有2e5个点，离散化；类型数量最多2e5，但每个类型可能要算“出现次数的幂”，快速幂。

具体步骤如下：

1. 收集所有pos_i，排序去重，得到压缩坐标数组xs。
2. 建立桶cnt_type，按每个位置统计各类型出现次数。因为类型值也可能很大，我同样把type_i收集起来做个离散化映射，这样“类型”也变成0..k-1的编号。
3. 从左到右按位置扫描。每到一个位置，对每个类型的出现次数，用快速幂计算type_val ^ count % MOD，乘到当前位置的贡献里。
4. 对“当前位置之前所有位置“的贡献做前缀积（或者前缀和，取决于题面问的是乘积还是加和；我这边是乘积之和，就边扫边乘）。
5. 最后输出每个位置的答案。

里面有一个可以优化的点：类型值的离散化也可以复用同一个all数组（把type也一并塞进去）。只要你在排序前把所有需要映射的值全部放进去，后续二分定位时一个lower_bound就能同时解决“位置编号”和“类型编号”，代码少写一半，也不容易搞混。

实际提交时，我第一版就犯了个错：cnt_type数组开了1e9+1大小，直接编不过。后来改成类型离散化，内存立刻正常。这其实特别典型——初学者经常在处理“数值范围”时忘了去重，把离散化只用在坐标上，类型却当成小范围处理，结果在内存上栽跟头。记住：值域太大，不管它是什么含义，统一离散化才是王道。

还有一次WA是因为“每个位置左侧”的理解偏差。我一开始只统计了左侧，没包含当前位置，结果样例错得离谱。看了题目三遍才发现是“含本位置”。这些都是题目理解的边界问题，跟算法本身关系不大，但调试时很容易被误导成“取模出错”或者“快速幂写错了”，浪费大量时间。

如果你之前做类似的题总是差一口气，我的建议是别急着刷难题，先把这篇文章里的快速幂模板和离散化模板各抄十遍，直到手能默写。然后随便找一道数据范围巨大的水题，刻意用这两个工具去解，感受一下“压缩”之后代码的简洁程度。有了这两个基本功垫底，后面上树状数组、线段树、扫描线这些重型工具时，你会轻松很多——因为它们全都是建立在“坐标已经被处理得干干净净”的前提上的。