第一次在洛谷刷到 P5367 的时候，我盯着题面上“【模板】康托展开”这六个字看了好一会儿。康托展开？这名字听着就比线段树、树状数组抽象，结果点开题解一看，核心逻辑居然简单到可以用一句话说清：给你一个从 1 到 n 的排列，问它在所有全排列里按字典序排第几。反过来，给你一个名次，也能还原出原排列。就这么个看似简单的东西，却是信奥里排列枚举、状态压缩、甚至八数码问题里的常客，值得花点时间彻底吃透。
这篇文章我就把自己从零手写 P5367 的完整过程还原一遍，包含公式推导、树状数组优化、AC 代码、逆康托展开以及我调试时踩过的坑。适合刚接触排列类算法的选手，也适合那些“看过题解但没真正理解为什么这么写”的朋友。
1. 先搞清楚 P5367 在考什么，以及康托展开的用处
很多人第一次接触“康托展开”这个概念，第一反应是背公式。我之前也是这么干的，结果隔两周再写，又忘了。后来才意识到，这玩意儿本质上就是一个“字典序排名计数器”，它的定义和我们的直觉是完全一致的。
1.1 从一个具体排列说起：排名是什么
假设 n = 3，1 到 3 的全排列按字典序排出来是：
- 1 2 3
- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2
- 3 2 1
这种顺序大家应该都熟悉，就是一个一个数字比大小，跟查英文词典差不多。现在我问你：排列 (2,1,3) 排第几？一眼扫过去，第三。那如果 n = 10，给你一个随机排列，比如 (3,1,4,2,5,9,8,7,6,10)，你还想一眼看出来吗？几乎不可能。
康托展开要解决的就是这个问题：给定排列 p，快速计算它是第几个排列。题目 P5367 的 n 最大能到 10^6，所以不可能把全排列枚举出来，必须用 O(n log n) 甚至 O(n) 的做法。这也是为什么题目叫“模板”——它考察的是一种固定套路，理解了就一劳永逸。
1.2 除了刷题，这玩意儿还能用在哪儿
康托展开在实际竞赛里最常见的两个用途：一是状态压缩，比如某个搜索状态是一个排列，我想给每种排列分配一个唯一的整数 ID 作为访问标记，就可以用康托展开把排列映射成编号，数组比哈希表快得多；二是全排列枚举，有时题目要求“从小到大输出第 k 个排列”，这时候逆康托展开直接构造答案。
另外，著名的八数码问题里，棋盘状态可以抽象成一个 0 到 8 的排列，用康托展开压缩状态，配合 BFS 或者 A* 就能跑。换句话说，你如果打算打区域赛或者准备 NOIP 提高组，康托展开和逆康托展开算是排列类问题的基本功。
1.3 P5367 的具体数据范围与要求
P5367 题目本身给了一个排列，让你输出它的排名对 998244353 取模。这里有两个关键点：
- 排名从 1 开始。也就是说最小的排列 (1,2,3,...,n) 的排名是 1，而不是 0。
- n 最大 10^6，所以阶乘必须预处理，所有中间计算要对 998244353 取模，防止爆 long long。
明白了这两点，后面的公式和代码才有意义。
2. 公式背后的数学逻辑：排名为什么能拆成“阶乘和”
我先直接给出康托展开的公式，然后再一步步拆解，确保你不仅会背，还能理解每一项是怎么来的。
对于一个排列 p = (p1, p2, ..., pn)，它的字典序排名满足：
rank = 1 + Σ cnt_i × (n - i)!
其中 cnt_i 表示“在位置 i 之后，且数值比 p_i 小的数字个数”。
2.1 为什么是“后面有几个更小的数”
以排列 (2,1,3) 为例：
- i = 1，p1 = 2。在它后面比 2 小的数字有 1，所以 cnt_1 = 1。
- i = 2，p2 = 1。后面没有比 1 小的数字，cnt_2 = 0。
- i = 3，p3 = 3。后面没有数字，cnt_3 = 0。
套公式：rank = 1 + 1 × 2! + 0 × 1! + 0 × 0! = 1 + 2 = 3。跟前面表格里对上了。
那这一项 1 × 2! 到底代表什么？我在草稿纸上画了挺久才想通。你要计算 (2,1,3) 的排名，本质上是在数“有多少排列排在它前面”。排在它前面的排列，字典序都比它小，那么一定存在某个位置 i，前面 i-1 位和 (2,1,3) 完全相同，而第 i 位更小。
对于 i = 1，第一位可以是任何比 2 小的数字，也就是只有 1 这一种选择。第一位确定成 1 之后，剩下两个位置可以任意排列，有 2! 种方式。所以第一位就决定了 1 × 2! = 2 个排列排在 (2,1,3) 前面，也就是 (1,2,3) 和 (1,3,2)。
对于 i = 2，第二位要小于 p2 = 1，但前面第一位必须还是 2，第二位比 1 小的数字不存在，贡献为 0。i = 3 同理。
2.2 每一位贡献的精确含义
我需要强调一个容易被忽略的细节：cnt_i 不是“所有没出现过的比 p_i 小的数字个数”，而是“位置 i 后面还没被使用过、且比 p_i 小的数字个数”。因为在计算第 i 位时，前面 i-1 位已经固定了，那 i-1 个数字就不能再参与第 i 位的替换了。
举个例子，n = 4，排列 (4,1,2,3)。第一位是 4，后面比 4 小的数字有 1、2、3，共 3 个。所以第一位贡献 3 × 3! = 18。这 18 个排列指的是：第一位固定为 1、2、3 中任意一个（3 种选法），后三位任意排列（3! 种），共 18 种。它们全部排在 (4,1,2,3) 前面。
到第二位时，p2 = 1，后面比 1 小的数字已经没有了，贡献为 0。继续往后扫，每一位的贡献都是 0。最终 rank = 1 + 18 = 19。你手动排一下 1 到 4 的 24 个排列也会发现，(4,1,2,3) 恰好是第 19 个。
2.3 阶乘数组的正确预处理方式
预处理阶乘是最容易写错的地方，特别是 0! 的定义。C++ 里数组下标从 0 开始，所以：
fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
这里 fac[i] 对应 i!。当 n = 10^6 时，fac 数组开到 10^6 + 5 就够了，别用 vector 然后 push_back（虽然能用，但没必要）。
我在实际做题时还遇到过一个坑：直接用 int 存 fac[i]，结果 n 稍微大一点就溢出了。因为虽然每一步都取模，但 fac[i - 1] * i 这一步在乘法时已经可能超过 int 范围。所以 fac 数组一定要用 long long，或者每一步强转 long long。后面算 ans 时同理。
3. 从 O(n²) 到 O(n log n)：树状数组在展开里扮演的角色
公式本身很好理解，但如果你直接照着公式写，每到一个位置都扫描一遍后面的数字数有多少比它小，复杂度就是 O(n²)。n = 1000 可能还无所谓，n = 10^6 直接超时。所以 P5367 考察的第二层东西是：怎么快速统计“当前剩余数字中有多少个数小于 p_i”。
3.1 动态维护剩余数字的思路
需要一个数据结构，支持两种操作：
- 查询：当前还没被“消耗”掉的数字中，有多少个小于 x。
- 删除：某个数字 p_i 已经用在排列前面了，之后不能再参与统计。
这个场景下最常见的做法就是树状数组。初始化时把所有数字 1 到 n 都标记为“存在”，即对每个位置 add(i, 1)。然后遍历排列：
- 查询小于 p_i 的剩余数字个数，即 sum(p_i - 1)，把结果加到答案里。
- 删除 p_i，即 add(p_i, -1)。
为什么这里用树状数组而不是线段树？因为树状数组代码短、常数小、内存占用低。线段树当然也能做，但模板题没必要把自己的代码写得又长又难调。树状数组的查询和修改都是 O(log n)，整体 O(n log n)，稳稳过 10^6 的数据。
3.2 lowbit 和树状数组的“为什么”
如果你对树状数组本身还不太熟，我来补一个最关键的直觉。树状数组的核心是 lowbit 操作，lowbit(x) = x & -x，表示 x 的二进制表示里最低位的 1 所对应的值。
add(pos, val) 的操作是从 pos 开始，每次 pos += lowbit(pos)，把所有覆盖 pos 的区间都更新一遍。sum(pos) 的操作是从 pos 开始，每次 pos -= lowbit(pos)，累加所有相关区间的和。这个过程很像爬楼梯，每步跨的幅度恰好是当前二进制位最低位 1 的大小。
我刚开始学树状数组时，总觉得 lowbit 是个魔法。后来画了一张长为 8 的数组图，把每个 bit[i] 负责的区间写出来，就全明白了。这里我不画图，用文字描述：bit[1] 管 [1,1]，bit[2] 管 [1,2]，bit[3] 管 [3,3]，bit[4] 管 [1,4]，bit[5] 管 [5,5]，bit[6] 管 [5,6]，bit[7] 管 [7,7]，bit[8] 管 [1,8]。查询 [1,7] 的和 = bit[7] + bit[6] + bit[4]，正好是 7 -> 6 -> 4 这条递减链。修改位置 3 时，需要更新 bit[3]、bit[4]、bit[8]，恰好是 3 -> 4 -> 8 这条递增链。逻辑是自洽的。
3.3 展开时的操作顺序：先查再删，不能反过来
这个顺序问题，我犯过错。假设先执行 add(p_i, -1) 再查询 sum(p_i - 1)，那 p_i 本身就已经被删掉了。问题是 p_i 不小于 p_i，查询的是小于 p_i 的数，按理说 p_i 不在统计范围内，先删后查似乎也没问题。
但你再想一步：如果排列里出现重复值，或者某些题目的排列不是 1 到 n 的完整排列而是部分排列，顺序就可能有影响了。更关键的是，先查再删在逻辑上更加清晰：查询时，当前未删除集合 = 从第 i 位开始往后所有还“活着”的数字。你把 p_i 删掉，正好对应“p_i 已经安排到前面位置了”。所以标准顺序是：
int smaller = bit_sum(p_i - 1); ans = (ans + smaller * fac[n - i]) % MOD; bit_add(p_i, -1);
我在 P5367 的讨论区看到有人把顺序写反，结果 WA 了还找不到原因。这类模板题，操作顺序就是命门。
4. 完整 AC 代码：P5367 的 C++ 实现与逐段注释
这部分给出我最终提交通过的代码，然后逐段解释关键细节。代码风格偏竞赛向，直接可读、可复制。
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MOD = 998244353; const int MAXN = 1000005; int n; int a[MAXN]; int bit[MAXN]; ll fac[MAXN]; int lowbit(int x) { return x & (-x); } void bit_add(int idx, int val) { while (idx <= n) { bit[idx] += val; idx += lowbit(idx); } } int bit_sum(int idx) { int res = 0; while (idx > 0) { res += bit[idx]; idx -= lowbit(idx); } return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } fac[0] = 1; for (int i = 1; i <= n; i++) { fac[i] = fac[i - 1] * i % MOD; bit_add(i, 1); } ll ans = 0; for (int i = 1; i <= n; i++) { int smaller = bit_sum(a[i] - 1); ans = (ans + (ll)smaller * fac[n - i]) % MOD; bit_add(a[i], -1); } printf("%lld\n", (ans + 1) % MOD); return 0; }4.1 读入与初始化：为什么用 scanf 而不是 cin
n 最大 10^6，用 cin 配合 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 其实也能过，但我个人习惯在这类大输入量的模板题里直接上 scanf。原因不是 cin 一定超时，而是 scanf 更稳妥，不用记着关同步，也不会因为某些评测环境的输入流问题翻车。
初始化部分做了两件事：预处理阶乘数组 fac，同时把 1 到 n 全部插入树状数组。这两个操作可以合在同一个循环里，省一次遍历。
4.2 核心循环的计算顺序
遍历排列的每一位：
- 查询 bit_sum(a[i] - 1)，得到当前剩余数字中小于 a[i] 的个数。
- 乘以 fac[n - i]，累加到 ans。
- 从树状数组中删除 a[i]。
这里的 fac[n - i] 对应公式中的 (n - i)!。注意系数转成 ll 再乘，防止 int 乘法溢出。ans 每轮都取模，虽然中间结果不会爆 ll，但取模是好习惯。
4.3 输出时为什么加 1
因为公式里 rank = 1 + Σ...，而我们累加时没有处理那个“+1”，所以最后输出 (ans + 1) % MOD。这里有个小坑：如果 ans + 1 恰好等于 MOD，取模后变成 0，但实际排名怎么可能是 0 呢？其实不会，因为 n 个排列的排名最大是 n!，而 n! 通常远大于 MOD，取模后出现 0 是正常的，题目要的就是取模后的结果。所以直接 (ans + 1) % MOD 没问题，别画蛇添足判断。
5. 反向推导：逆康托展开与树状数组上的二分
讲完正向展开，逆康托展开几乎是必然配套的内容。题目 P5367 只要求正向，但很多排列枚举的题会用到反向，比如“输出字典序第 k 个排列”。理解逆过程能反过来加深你对正向公式的理解。
5.1 逆康托展开的核心思路
已知 n 和排名 k（从 1 开始），要还原排列。先把 k 减 1，得到一个从 0 开始的编号 r。然后从第一位开始：
- 当前剩余数字集合 S，初始为 {1,2,...,n}。
- 第 i 位的候选数字中，跳过 t = r / (n - i)! 个未使用的数字，取第 (t+1) 个小的数字。
- 令 r = r % (n - i)!。
为什么？因为正向公式里，第 i 位贡献是 cnt_i × (n - i)!。现在反过来，r 里面包含了所有比它小的排列数，除以 (n - i)! 就能反推出 cnt_i，也就是“在第 i 位之后有多少个比 p_i 小”。从剩余集合的角度看，cnt_i 恰好等于跳过多少个未使用的数字。
5.2 树状数组上找第 k 个未使用数字
找“第 k 个未使用的数字”可以用树状数组加二分，复杂度 O(log n) 单次，总 O(n log n)。直接二分位置，如果 bit_sum(mid) >= k，说明前 mid 个数字里至少有 k 个未使用，收缩右边界。但这样每次是 O(log² n)，对 n = 10^6 来说勉强能过，不够优雅。
更好的做法是倍增跳 lowbit。思路类似求 LCA 的倍增：从高位二进制往下试探，找最大的 pos，使得 bit_sum(pos) < k，最终 pos + 1 就是所求。这个写法有点绕，我给出完整代码：
int find_kth(int k) { int pos = 0; for (int i = 18; i >= 0; i--) { int nxt = pos + (1 << i); if (nxt <= n && bit[nxt] < k) { pos = nxt; k -= bit[nxt]; } } return pos + 1; }这里的 18 是因为 n <= 10^6 < 2^20，取 18 或者 20 都行，取一个能覆盖 n 的最大幂即可。判断 bit[nxt] < k 而不是 <=，是为了让 pos 停在“前缀和恰好小于 k 的最后一个位置”，这样 pos + 1 就是第 k 个数字。
我在第一次写这个函数时，把条件写成 bit[nxt] <= k，结果找出来的数字偏后一位，调了半天才发现是边界问题。记住：要找第 k 个，前缀和等于 k 的位置已经包含目标，所以不能等于。
5.3 逆展开完整示例
用 n = 3，k = 3，期望还原 (2,1,3)。
- r = 2，fac[2] = 2，t = 2 / 2 = 1，剩余集合 {1,2,3}，跳过 1 个数字，取第 2 个 = 2。r = 2 % 2 = 0。
- r = 0，fac[1] = 1，t = 0 / 1 = 0，剩余集合 {1,3}，取第 1 个 = 1。r = 0 % 1 = 0。
- 剩余 {3}，取 3。
得到 (2,1,3)，正确。
6. 实测过程中遇到的坑与调试心得
最后这块是我想重点分享的，毕竟模板题不是背下来就完事，真正动手写的时候总会有各种意想不到的问题。
6.1 数据溢出：一眼看不出来的 WA
我第一次交 P5367 时，fac 数组开的是 int，代码长这样：fac[i] = fac[i - 1] * i % MOD。fac[i - 1] * i 这两个 int 相乘时，结果可能已经超过 2^31 - 1，再做 % 操作其实在未定义行为边缘试探。改成 long long 后就过了。这个问题我看很多新手都会踩，因为在小数据上根本没区别，一旦 n 到 10^6，溢出就冒出来了。
6.2 快读问题：scanf 和 cin 的取舍
如果你选择用 cin，记得加这两行：
ios::sync_with_stdio(false); cin.tie(nullptr);
否则 10^6 的读入在某些评测机上可能直接 TLE。我自己的习惯是 scanf，简单粗暴不纠结。理论上还可以用 fread 手写快读，但对于这道题完全没必要，scanf 已经够快。
6.3 阶乘数组的边界：fac[0] = 1 千万别忘
很多人预处理阶乘直接从 1 开始，循环里写 fac[1] = 1，然后发现最后一位的系数算错。康托展开在算到最后一位时用的是 (n-n)! = 0! = 1，所以 fac[0] = 1 必须设置。P5367 里最后一位的贡献虽然永远是 0（因为后面没有更小的数），但逆展开、或者处理某些变体问题时，0! 是绕不开的。
6.4 树状数组开多大：MAXN 多开 5 到 10 个点
我开的是 const int MAXN = 1000005，因为 n 最大 10^6，多开 5 个位置防止边界越界。树状数组的 add 循环条件 idx <= n，所以 bit 数组一定不能只开 n 个，要开到 n + 1 以上。很多 RE 都是数组开小了，并不是算法写错。
6.5 我在本地自测的验证脚本
为了确认代码正确，我写过一个暴力验证：枚举 n = 1 到 8 的所有排列，用 next_permutation 生成排列，记录它们的编号，再用康托展开算编号，比对结果。这种“暴力对拍”是刷模板题最好的学习方法。你可以把暴力代码和康托展开代码分开编译，然后生成随机排列塞进去对比输出。可惜我当年偷懒没做，后来在 n = 7 的时候才发现逆展开的二分条件写错了。
对拍的具体做法不复杂：main 函数里跑两层循环，外层枚举 n，内层用 vector 存 1 到 n，do while(next_permutation(...)) 循环，每次把当前排列丢给康托展开函数，把返回值和一个自增计数器对比。任何 n 不超过 8 的小范围里跑几百个排列，就能把边界问题暴露干净。
6.6 模板题的后续扩展思路
如果你把康托展开吃透了，可以试着做几个变体：排列中有重复数字时的排名怎么算（需要除以重数的阶乘）；康托展开结合线段树求逆序对；逆展开配合动态维护集合解决“第 k 个排列”类题目。这些扩展本质上都是同一套思想，只是统计手段换一换。
我个人在实际刷题中的体会是：像康托展开这种模板题，不要光看题解，一定是自己把公式推到能默写的程度，然后不看代码独立实现一遍，再写一个逆康托展开验证正逆是否互逆。多来几轮，比刷十道同类题都管用。最后再分享一个小技巧：把树状数组、阶乘预处理、康托展开封装成三个独立的函数，以后遇到排列压缩的题直接复用，能帮你省下大量重复调试的时间。
