)
如果你去翻 NOIP 2016 普及组第四题《魔法阵》的讨论区，一定会看到这样的话：“我四层 for 都写出来了，为什么还是 0 分？”我第一次做这题时也卡了很久。题目要求统计 n 个魔法物品分别作为 A、B、C、D 的次数，看起来就是最朴素的四元组计数，但 n 到了几万量级，四层循环根本跑不动。更折磨人的是，这题不是光会枚举就能过，它需要你先看懂题面里三个条件的数学含义，然后才能想到用前缀和、后缀和去优化。
这篇文章就围绕魔法阵这道题的“难点解决”来写：先从题目条件讲起，解释为什么四重循环必炸；再把 A/B 和 C/D 拆成两个二元组，推导出 O(m²/9) 的做法；最后附上完整 C++ 代码和我实际提交时踩过的坑。无论你是准备 NOIP、CSP-J 还是单纯想练组合计数，这篇都能直接照着复现，省去你自己绕弯路。
1. 魔法阵最劝退的地方：题目读完，四层循环根本不敢写
1.1 原题到底要我们数什么
先把题意捋顺。有一堆魔法物品，每个物品有一个魔法值 X。要找一个四元组，四个物品分别叫 A、B、C、D。四元组必须满足：
- Xa < Xb < Xc < Xd；
- Xb - Xa = 2 * (Xd - Xc)；
- Xb - Xa < (Xc - Xb) / 3。
注意输出要求很特殊：不是让你输出“总共有多少个魔法阵”，而是让你输出每个物品分别作为 A、B、C、D 出现了多少次。也就是说，如果有多个魔法阵都包含同一个物品，这个物品对应角色的计数都要累加。
这导致一个直观想法会立刻浮上来：枚举 A、B、C、D 四个下标，检查条件，然后给四个物品的对应答案加 1。这个思路在数学上完全正确，但实际样例一上，就等着超时吧。
1.2 把三个条件画到数轴上
做组合计数题，第一步永远是先看条件能不能化简。原题三个条件很繁琐，但放到数轴上看就清楚多了。
设：
t = Xd - Xc
因为 Xa < Xb < Xc < Xd，所以 t 是正整数。于是第二个条件变成：
Xb - Xa = 2t
第三个条件：
2t < (Xc - Xb) / 3
两边乘 3，得到：
6t < Xc - Xb
因为魔法值都是整数，所以更准确的写法是：
Xc >= Xb + 6t + 1
把这几个式子组合起来，数轴上的距离关系就非常清晰了：
- A 到 B 的距离是 2t；
- B 到 C 的距离至少是 6t+1；
- C 到 D 的距离是 t。
也就是说，一旦固定了 t，整个四元组在值域上的分布就固定下来了。A 和 B 距离近，C 和 D 距离近，但 B 和 C 之间必须隔开很大一段。
1.3 复杂度第一关：四边形枚举必炸
如果你直接四层循环枚举四个下标，即使排序后加上剪枝，复杂度也是 O(n^4)。n 到几百就够呛，更别说题目数据是几万级别，O(n^4) 跑完需要的时间可以用“天”来计算。
稍微聪明一点的做法是枚举 A 和 B，然后根据条件确定 C 和 D 的范围，再用循环累加。这大概是把 O(n^4) 降到了 O(n^3) 左右，仍然过不了大样例。因为题目想逼你做的事，不是少一层循环，而是换一种计数方式：不要按“四个点”去枚举，要按“差值 t”去枚举。
这也正是魔法阵这道题被放在普及组压轴位置的原因：它考的不是某个高级数据结构，而是你能不能从一堆不等式里抽出一个可优化的结构。
2. 断掉四元组：把 A/B 和 C/D 看成两个绑定的二元组
2.1 设 t = Xd - Xc 之后，数轴长这样
刚才已经推出：
- Xb = Xa + 2t；
- Xc >= Xb + 6t + 1；
- Xd = Xc + t。
在数轴上画一下，大概是：
A — 2t — B — 至少 6t+1 — C — t — D
这个结构非常有意思：A 和 B 绑在一起，C 和 D 绑在一起，中间隔着一大段空白。也就是说，对于固定的 t，如果我们已经确定了一对合法的 A/B，那么任何一对满足 Xc > Xb + 6t 的 C/D 都能拼成一个魔法阵。
反过来说，如果我们先确定了一对合法的 C/D，那么任何一对满足 Xb <= Xc - 6t - 1 的 A/B 也都能拼成一个魔法阵。
A/B 和 C/D 之间的选择，只有“B 的值和 C 的值之间距离足够大”这一个约束，中间没有其它交叉条件了。这就是拆开的关键。
2.2 为什么固定 t 后 A/B 与 C/D 互不干扰
很多初学者会卡在这里：A/B 和 C/D 看起来明明是互相影响的，怎么说独立就独立？
其实没有完全独立，它们还受一个条件约束：B 与 C 的差值必须大于 6t。只不过这个条件只取决于 B 和 C 的值，和具体选哪个 A、哪个 D 没有关系。
换句话讲：
- 对于一对 A/B，只要知道它的 B 值，就能确定“哪些 C 能配”；
- 对于一对 C/D，只要知道它的 C 值，就能确定“哪些 B 能配”。
所以我们可以分别统计所有 A/B 组合和所有 C/D 组合，然后按 B 和 C 之间的位置关系做乘法。
用 t 来表示差值，A/B 的组合长这样：
AB[b] = cnt[b - 2t] * cnt[b]
意思是，以 b 作为 B 值时，A 必须是 b - 2t，那么 a 值有 cnt[b-2t] 种选法，b 值有 cnt[b] 种选法，这一对 A/B 就有 cnt[b-2t] * cnt[b] 种组合。
C/D 的组合长这样：
CD[c] = cnt[c] * cnt[c + t]
以 c 作为 C 值时，D 必须是 c + t，同样用乘法。
现在的问题就变成了：把 AB[b] 和 CD[c] 这两串值算出来，然后按条件“B 和 C 之间至少隔了 6t+1”配对计数。
2.3 先写出不优化的朴素公式
如果不优化，我们可以枚举每一个 B 值，然后内层枚举每一个合法的 C 值。伪代码如下：
for (int t = 1; t <= m; ++t) { for (int b = ...; b <= ...; ++b) { for (int c = b + 6 * t + 1; c <= m - t; ++c) { // AB组合数 * CD组合数，累加到答案上 } } }这样还是 O(m^3) 量级，因为外层 t、中层 b、内层 c 都是值域大小级别的循环。但观察一下内层这个循环：当 b 固定之后，c 的合法范围是 b+6t+1 到 m-t，我们要算的是这一段里所有 CD[c] 的和。连续一段的和，不就是前缀和或后缀和最擅长的东西吗？
所以下一步很自然：用后缀和把所有 CD 求出来，用前缀和把所有 AB 求出来，两个线性扫描一拼，整个算法就变成了两重循环。
3. 让朴素公式跑起来：前后缀和 O(m²/9) 推导
3.1 后缀和：一口气算出所有 C/D 组合
对于固定 t，我们先预处理一个数组 suf：
suf[x] = cnt[x] * cnt[x+t] + cnt[x+1] * cnt[x+1+t] + ... 一直加到 x+t 不超过 m
也就是从 x 开始，所有合法 C/D 组合数的后缀和。
计算方式很简单，从后往前扫：
for (int x = m - t; x >= 1; --x) { suf[x] = suf[x + 1] + 1LL * cnt[x] * cnt[x + t]; }为什么只扫到 m - t？因为如果 x + t > m，D 值超出上限，不可能存在合法的 C/D 组合。
有了 suf 之后，假设 B 的值为 b，那么合法 C 的范围是：
c >= b + 6t + 1
同时，c 最大只能是 m - t。这一段里所有 C/D 组合数就是：
suf[b + 6t + 1]
这是一个 O(1) 的查询。
3.2 前缀和：一口气算出所有 A/B 组合
同样的思想，我们再预处理一个前缀和数组 pref：
pref[x] = AB[1] + AB[2] + ... + AB[x]
其中 AB[b] = cnt[b - 2t] * cnt[b]，表示以 b 为 B 值的 A/B 组合数。
计算方式：
for (int b = 1; b <= m; ++b) { pref[b] = pref[b - 1]; if (b >= 2 * t + 1) { pref[b] += 1LL * cnt[b - 2 * t] * cnt[b]; } }注意，b 至少要 2t+1，否则 b - 2t 小于 1，没有合法的 A 值。
对于某个 C 值 c，合法的 B 需要满足：
b <= c - 6t - 1
那么所有能配上这个 C 的 A/B 组合数就是：
pref[c - 6t - 1]
同样是一个 O(1) 查询。
3.3 两条扫描线合流，累加四个角色
现在把两个式子合起来。
先看 B 对 A、B 自身的贡献。
固定 t，对于一个 B 值 b：
- A 的值是 a = b - 2t；
- 所有合法 C/D 组合数是 suf[b + 6t + 1]；
- 每个 A 物品可以搭配 cnt[b] 个 B 物品，所以对 A 的贡献是 cnt[b] * suf[b + 6t + 1]；
- 每个 B 物品可以搭配 cnt[a] 个 A 物品，所以对 B 的贡献是 cnt[a] * suf[b + 6t + 1]。
再固定 C 值 c：
- D 的值是 d = c + t；
- 所有合法 A/B 组合数是 pref[c - 6t - 1]；
- 每个 C 物品可以搭配 cnt[d] 个 D 物品，所以对 C 的贡献是 cnt[d] * pref[c - 6t - 1]；
- 每个 D 物品可以搭配 cnt[c] 个 C 物品，所以对 D 的贡献是 cnt[c] * pref[c - 6t - 1]。
这里有个非常容易想错的地方：题目要输出的是“每个物品作为某个角色的次数”，所以我累加的都是“单个物品”的次数，没有额外乘当前角色自己的 cnt。如果你把总的角色出现次数累到一个数上，输出前再除以对应角色的 cnt，理论也行，但很容易因为整除和边界搞错。直接按单个物品累加，输出时照抄就行。
3.4 可直接提交的 C++ 代码
完整代码如下，我加了一些注释，重点标注边界条件。
#include <bits/stdc++.h> using namespace std; const int MAXN = 40005; int n, m; int val[MAXN], cnt[MAXN]; long long ansA[MAXN], ansB[MAXN], ansC[MAXN], ansD[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> val[i]; ++cnt[val[i]]; } // t 表示 Xd - Xc，也就是 C 到 D 的距离。 // 极限情况下，A 可以取 1，于是 D 的最小值是 9t + 2，所以 9t + 2 <= m。 for (int t = 1; 9 * t + 2 <= m; ++t) { // suf[x]：C >= x 且 D = C + t 的所有 (C,D) 组合数 vector<long long> suf(m + 3, 0); for (int x = m - t; x >= 1; --x) { suf[x] = suf[x + 1] + 1LL * cnt[x] * cnt[x + t]; } // 通过 B 的取值，累加 A 和 B 的贡献 // b 至少是 2t+1，至多让 b + 7t + 1 <= m for (int b = 2 * t + 1; b + 7 * t + 1 <= m; ++b) { int a = b - 2 * t; long long wayCD = suf[b + 6 * t + 1]; if (wayCD == 0) continue; // 每个 A 物品可以配 cnt[b] 个 B 物品 ansA[a] += 1LL * cnt[b] * wayCD; // 每个 B 物品可以配 cnt[a] 个 A 物品 ansB[b] += 1LL * cnt[a] * wayCD; } // pref[x]：B <= x 的所有 (A,B) 组合数 vector<long long> pref(m + 3, 0); for (int b = 1; b <= m; ++b) { pref[b] = pref[b - 1]; if (b >= 2 * t + 1) { pref[b] += 1LL * cnt[b - 2 * t] * cnt[b]; } } // 通过 C 的取值，累加 C 和 D 的贡献 // c 至少是 8t+2，这样才能让 B 有最小值 2t+1 for (int c = 8 * t + 2; c + t <= m; ++c) { long long wayAB = pref[c - 6 * t - 1]; if (wayAB == 0) continue; // 每个 C 物品可以配 cnt[c+t] 个 D 物品 ansC[c] += 1LL * cnt[c + t] * wayAB; // 每个 D 物品可以配 cnt[c] 个 C 物品 ansD[c + t] += 1LL * cnt[c] * wayAB; } } for (int i = 1; i <= n; ++i) { cout << ansA[val[i]] << ' ' << ansB[val[i]] << ' ' << ansC[val[i]] << ' ' << ansD[val[i]] << '\n'; } return 0; }这个做法的复杂度是 O(m²/9)，m 表示魔法值的最大值，而不是物品个数。外层 t 最多到 m/9，内层两个循环都是 O(m)，所以总时间大概是 m² / 9 量级。对于 m 在几万以内的数据，完全够用。
4. 从 WA 到 AC：我踩过的三个坑
4.1 外层枚举上界写错，样例过了大数据死
我第一次写这段代码时，外层循环随手写成了：
for (int t = 1; t <= m; ++t)然后大数据直接超时，小样例还看起来没问题。后来冷静算了一下才发现，t 根本不可能取到 m，因为一个魔法阵里 A 到 D 的最小距离是 9t+1。
为什么是 9t+1？看数轴：
- A 到 B 是 2t；
- B 到 C 最小是 6t+1；
- C 到 D 是 t。
所以 A 到 D 最小距离是 2t + (6t+1) + t = 9t+1。这意味着如果 A 取最小值 1，D 至少是 9t+2。于是 t 必须满足：
9t + 2 <= m
也就是：
t <= (m - 2) / 9
如果 m 是几千，写成 t <= m 问题不大，就是额外空转很多次；如果 m 是几万，每多一倍的 t，内层就要多扫一整轮，超时就很正常了。
这个上界不是玄学，是从不等式一步推出来的，写代码前应该先算清楚。
4.2 同值魔法物品的乘法，乘多乘少都不对
题目里的魔法值可能有重复，比如两个物品的魔法值都是 5。它们在同一个魔法阵里不可能同时出现，因为 Xa < Xb < Xc < Xd 要求四个位置的值严格递增，同值物品不能占两个角色。
但同值物品会导致计数的乘法关系。假设 cnt[3] = 2，表示魔法值等于 3 的物品有两个。当某个 B 值 b 需要配 A 值 3 时，每个 B 物品都有 cnt[3] = 2 种 A 物品可选。
在代码里，我累加 A 的贡献时用的是：
ansA[a] += cnt[b] * wayCD;这里没有乘 cnt[a]，因为 ansA 存的是“单个魔法值为 a 的物品”的次数，而不是“所有魔法值为 a 的物品”的总次数。
有同学喜欢把 ansA[a] 存成总值，写成：
ansA[a] += cnt[a] * cnt[b] * wayCD;然后输出时再除以 cnt[a]。这种做法不是不行，但两个问题：
- 如果 cnt[a] = 0，除法会出现除零异常；
- 如果中间过程中某个 cnt[a] 没有完全整除，最后输出会差 1 或 2，非常难排查。
所以我的建议是：从一开始就明确“数组存的是单物品次数”，后面的所有加法都按单物品的角度来写，输出时完全不用处理倍数。
4.3 int 溢出、下标越界和输出顺序
第三个坑是基本功，但很致命。
魔法阵的总数量在 n 很大时会非常大。n 是几万量级，所有可能的四元组数量是组合数级别，早已超过 int 范围，所以 ansA、ansB、ansC、ansD 必须开 long long。中间乘法的 cnt[b] * wayCD 也要小心，强烈建议写成 1LL * cnt[b] * wayCD，防止编译器先用 int 乘完再转 long long。
下标越界也容易出现在 suf 和 pref 的访问上。比如 b + 6t + 1 可能超过 m，这时候如果数组开小了，程序直接崩；如果碰巧没崩，读到的也是一个脏数据。稳妥做法是数组开到 m + 3，并且在循环条件里提前卡好边界。我代码里 b 的循环上界写的是 b + 7t + 1 <= m，正是为了保证访问 suf[b + 6t + 1] 时下标不会越界。
最后是输出顺序。题目要求每行四个数，分别是对应物品作为 A、B、C、D 的次数。这个顺序一旦搞反，全 WA。我自己对拍时经常栽在这一步，后来写了一个小暴力程序随机生成数据，才确认不是算法错了，而是输出顺序反了。
5. 这类“枚举差值+区间计数”的套路还能用在哪
5.1 四元组计数问题的通用拆法
魔法阵的核心思路，可以总结成一套方法论。
遇到四元组计数题，不要急着四层循环，先看条件能不能拆成“两个二元组”。如果四个元素之间存在两个独立的小结构，中间只靠一个“大小位置关系”连接，那大概率可以用前缀和或后缀和优化。
固定一个差值 t，把 A/B 和 C/D 分别看成两个整体：
- A/B 二元组只和 B 的值有关；
- C/D 二元组只和 C 的值有关；
- 拼合条件只剩“B 和 C 之间距离足够大”这一个不等式。
这时候所有四元组数量就可以拆成：
四元组数量 = 每个合法 A/B 组合数 × 对应范围内所有 C/D 组合数
或者反过来：
四元组数量 = 每个合法 C/D 组合数 × 对应范围内所有 A/B 组合数
分别用前缀和、后缀和预处理，复杂度直接从 O(n^4) 跳到 O(m²) 甚至更低。
5.2 从魔法阵到其它竞赛题的迁移
这个套路在很多题里都能看到。比如一些组合计数的题目会要求统计满足多个不等式的四元组，或者统计满足差值关系的二元组配对，核心都是“拆二元组 + 区间统计”。
备赛的时候，可以把魔法阵和 NOIP 2016 提高组的《愤怒的小鸟》拿出来一起练。魔法阵考的是数学建模和前缀和优化，愤怒的小鸟考的是状态压缩 DP，两题都对“枚举方式的选择”非常讲究，能帮你建立起“先分析条件，再选算法”的做题习惯。
另外，这类题还特别适合练对拍。写一个 O(n^4) 的暴力版，限制 n <= 10，然后随机生成小数据，和自己的优化版跑同一组输入，比对输出。对拍能查出的问题往往是你自己盯半天都看不出来的边界 bug。
5.3 备赛时怎么练这道题
如果你想真正吃透魔法阵，建议按这个顺序练：
- 第一天：不看题解，先把题目条件抄一遍，自己在纸上推出 A/B/C/D 之间的距离关系；
- 第二天：尝试写 O(n^3) 版本，确认时间复杂度不对，但用来验证小数据；
- 第三天：按本文思路写 O(m²/9) 版本，重点体会前缀和和后缀和的构造过程；
- 第四天：关上题解，重新默写一遍完整代码，包括所有边界条件。
这道题的价值不在于代码本身，而在于那个“从枚举四个点，到枚举一个差值，再到两个区间统计”的思维转变。想通这一步之后，再遇到表面上很复杂的组合计数题，你就不会再怕了。
我当时踩完那几个坑之后，最大的体会是：竞赛题里最难的部分往往不是算法，而是把题目条件翻译成一个能动手优化的数学结构。魔法阵就是最好的例子。
