AtCoder Beginner Contest 168 的 E 题“∙ (Bullet)”一眼看上去像个物理题实际上是一道把向量几何和组合计数结合得很漂亮的题目。题目给了 N 条鱼每条鱼有两个属性 A_i 和 B_i如果两条鱼满足 A_i * A_j B_i * B_j 0就不能同时出现在渔网里问一共有多少种合法的抓鱼方案。这道题适合刚接触 AtCoder 中档题的选手也适合想复习组合计数、约分技巧和模运算经验的人它不考什么冷门算法难点全在思路转化和细节处理上。我第一次做这题时第一反应是“冲突关系能不能建图能不能用并查集”结果发现这题根本不能这样玩冲突关系不是传递的A 和 B 冲突、B 和 C 冲突不代表 A 和 C 冲突图论模型直接报废。后来老老实实把每个属性对当成向量才发现所有东西都顺了。1. 题目到底在问什么内积为零的两条鱼不能同时出现1.1 从属性对到二维向量题目给的条件是 A_i * A_j B_i * B_j 0这个式子如果你在高中认真学过向量应该一眼就能认出来这是两个二维向量 (A_i, B_i) 和 (A_j, B_j) 的内积。内积为零的几何含义就是两个向量互相垂直。所以在题意转化之后问题变成平面上有 N 个向量选一个非空子集使得子集中不存在两个互相垂直的向量问有多少种选法。这个转化是整个题的命根子。如果看不破这一点你会一直在“怎么维护这种奇怪的冲突关系”里打转看破了后面就是纯粹的统计问题。1.2 注意冲突是“垂直”不是“平行”这里有一个特别容易踩的误区很多人看到冲突条件后会把它类比成“同方向不能共存”然后按“相同或相反分成一组”来做。大错特错。方向相同或相反的向量不但能共存而且它们的内积一定不等于零。比如 (1,2) 和 (2,4) 方向相同内积是 12 24 10不冲突(1,2) 和 (-1,-2) 方向相反内积是 -1 - 4 -5也不冲突。真正冲突的是那种“一个往东一个往北”的关系。这个区别直接决定分组方式。如果是“平行不能共存”你只需要把共线的向量归成一组组内互斥但这里是“垂直不能共存”互斥关系是发生在“两个垂直方向之间”的这完全是另一套逻辑。想明白这一点之后我脑子里马上冒出一个问题方向这么多怎么把一个方向和它的垂直方向成对地找出来这就引出了下面的核心操作。2. 核心思路把 N 个向量按“方向”分组2.1 约分化简把所有向量归一化到同一个方向如果有两个向量 (2,4) 和 (1,2)它们虽然数值不同但方向完全一样。在计数时我们应该把这种方向相同的鱼放进同一个组里。最标准的做法是“规范化”也叫“归一化”先算出 g gcd(abs(x), abs(y))。把 x 和 y 同时除以 g。统一符号让第一个非零分量为正。举个例子(2,4) → 除以 gcd 2 → (1,2)(-2,-4) → 除以 gcd 2 → (-1,-2)然后第一个非零分量是负数整体取反变成 (1,2)(-2,4) → 除以 gcd 2 → (-1,2)第一个非零分量已经是负数保留 (-1,2)这样做完之后所有方向相同的向量都会变成同一个 pair直接扔进 map 里统计个数就行。这里有个小细节必须先处理掉如果一个向量是 (0,0)它没法规范化需要单独挑出来。因为它和任何向量的内积都是 0所以它是一个超级冲突源后面要特殊对待。还有一种边界情况是 x0 或 y0。比如 (0,-3)如果直接除以 gcd 会得到 (0,-1)然后因为第一个非零分量是 y此时 y-1 是负数需要把 y 取反变成 (0,1)。我在写 norm 函数时习惯先把 x0 的情况单独返回 (0,1)把 y0 的情况单独返回 (1,0)省得后面符号判断出问题。2.2 用 pair 作为 map 的 key规范化之后每个非零向量都变成了一个 pairint, int。我选用了 mappairint,int, long long 来统计每个方向的个数。为什么不直接用 unordered_map因为 pair 不是内置哈希类型用 unordered_map 需要手写哈希函数比较麻烦。这题 N 最多 2e5map 的 O(log N) 插入复杂度完全够用所以直接用 map 是最省心的选择。这一段统计代码看起来就是mappairint,int, long long cnt; long long zero 0; for (int i 0; i N; i) { long long a, b; cin a b; if (a 0 b 0) { zero; continue; } cnt[norm(a, b)]; }到这里我们已经把一个看似复杂的向量集合压缩成了若干个“方向桶”每个桶里有若干条鱼。剩下的问题就是这些方向桶之间哪些是互斥的哪些是独立的。3. 互斥配对与组合计数推导3.1 每个方向都有且只有一个“垂直方向”对于一个非零方向 (x, y)所有与它垂直的向量方向是 (y, -x) 的方向也就是 (-y, x)。举个例子就清楚了方向 (1,2)垂直方向是 (-2,1)。方向 (-1,2)垂直方向是 (-2,-1)这个向量规范化之后是 (2,1)。注意垂直方向也要做同样的规范化处理。也就是说如果 map 里存的是规范化之后的 pair那么找某个方向的垂直方向必须用规范化之后的 pair 去找否则会因为符号或者约分不一致而找不到。我封装了一个函数pairint,int perp(pairint,int p) { return norm(-p.second, p.first); }这样只要 p 是规范化过的perp(p) 也一定是规范化过的。现在所有非零方向都形成了一个一个的“配对”一个方向 p 和它的垂直方向 q 是互斥的。3.2 一个配对内的贡献怎么算假设方向 p 上有 cnt[p] 条鱼方向 q 上有 cnt[q] 条鱼。这两个方向的鱼不能同时选那么合法的选择有三种互斥情况只从 p 里选鱼从 cnt[p] 条鱼中选一个非空子集方案数是 2^{cnt[p]} - 1。只从 q 里选鱼从 cnt[q] 条鱼中选一个非空子集方案数是 2^{cnt[q]} - 1。p 和 q 都不选只有 1 种方案。把三种情况加起来得到这一个配对对答案的贡献是2^{cnt[p]} 2^{cnt[q]} - 1这里要特别提醒一下为什么不用乘法而用加法。因为这两个方向的鱼是互斥的你选了 p 方向的任何一条鱼就绝对不能选 q 方向的任何一条鱼反之亦然。互斥事件之间应该用加法原理而不是乘法原理。大多数第一次做这道题的人在这里会天然地写出乘法然后样例都过不了整个人开始怀疑人生。其实只要想清楚“p 选了 q 就不能选”这个约束就不会搞混。3.3 没有垂直方向的组怎么处理如果某个方向 p 的垂直方向 perp(p) 在 map 里根本不存在说明输入数据里没有任何一条鱼的属性在 p 的垂直方向上。那么 p 方向上的鱼就没有任何“天敌”它们可以随便选也可以不选。这种情况下贡献就是简单的 2^{cnt[p]}。你可能会觉得这没什么好说的但我第一次写的时候真的忘了这个分支结果样例都过得不完整。后来在调试时发现有一类方向的 cnt 一直没被计算进去才反应过来。处理整个配对的计算逻辑可以这样写setpairint,int done; long long ans 1; for (auto [p, c] : cnt) { if (done.count(p)) continue; auto q perp(p); long long ways; if (cnt.count(q)) { long long c1 c; long long c2 cnt[q]; ways (pow2[c1] pow2[c2] - 1 MOD) % MOD; done.insert(p); done.insert(q); } else { ways pow2[c]; done.insert(p); } ans ans * ways % MOD; }使用 done 集合的原因很简单避免同一个配对被算两次。比如 p 的垂直方向是 qq 的垂直方向必然又是 p当 for 循环遍历到 q 时如果不去重就会又把 p 和 q 这个配对算一遍答案就错了。4. 零向量和答案的最终拼装4.1 零向量是“超级冲突源”现在回到那个我们一开始就单独挑出来的 (0,0)。(0,0) 和任何向量的内积都是 0所以它和所有鱼都冲突。同时两条零向量之间也冲突因为 (0,0) 和 (0,0) 的内积也是 0。这意味着什么意味着你最多只能选一条零向量而且一旦选了零向量其他任何鱼都不能选。从计数角度来说假设有 zero 条零向量它们能提供的“新方案”其实只有 zero 种单独选第一条、单独选第二条、……、单独选第 zero 条。剩下还有一种“零向量一条都不选”的情况这个不需要单独加因为它已经被包含在“非零向量部分选法”的空集情况里了。4.2 把所有贡献组装起来现在你手里有两部分答案非零向量部分按前面第 3 章的配对方式相乘得到一个值 ans注意这个值里包含“非零部分一条都不选”的空集方案。零向量部分提供了 zero 种“只选一条零向量”的方案。但是题目要求非空集合。非零部分算出来的 ans 里包含的空集方案需要被减掉。所以最终答案是ans (ans zero - 1 MOD) % MOD;这里有一个很容易让人困惑的地方为什么不是 ans * (zero 1)因为零向量和其他任何向量都冲突它在逻辑上不是“每个方向组都可以独立选择”的关系而是一个“要么选一条零向量要么完全忽略零向量”的整体约束。如果非零部分已经选了至少一条鱼那么零向量必须一个都不选只有非零部分为空集时才允许去选那唯一一条零向量。用乘法会错误地允许“非零部分选着零向量也选着”的情况答案直接起飞。这道题 AC 代码的精华就在这里那一个减法。5. 完整代码与实现细节5.1 预处理 2 的幂代码里要多次用到 2^{cnt}而且 cnt 最大到 2e5所以我先预处理 pow2 数组vectorlong long pow2(N 1); pow2[0] 1; for (int i 1; i N; i) { pow2[i] pow2[i - 1] * 2 % MOD; }这样后面直接查表就行没必要做快速幂。5.2 C17 完整实现下面是我提交时用的完整代码加了注释#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; pairint,int norm(int x, int y) { if (x 0 y 0) return {0, 0}; if (x 0) return {0, 1}; if (y 0) return {1, 0}; int g gcd(abs(x), abs(y)); x / g; y / g; // 统一符号让第一个非零分量为正 if (x 0) { x -x; y -y; } else if (x 0 y 0) { y -y; } return {x, y}; } pairint,int perp(pairint,int p) { return norm(-p.second, p.first); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; mappairint,int, long long cnt; long long zero 0; for (int i 0; i N; i) { int a, b; cin a b; if (a 0 b 0) { zero; continue; } cnt[norm(a, b)]; } vectorlong long pow2(N 1); pow2[0] 1; for (int i 1; i N; i) { pow2[i] pow2[i - 1] * 2 % MOD; } setpairint,int done; long long ans 1; for (auto [p, c] : cnt) { if (done.count(p)) continue; auto q perp(p); long long ways; if (cnt.count(q)) { long long c1 c; long long c2 cnt[q]; ways (pow2[c1] pow2[c2] - 1 MOD) % MOD; done.insert(p); done.insert(q); } else { ways pow2[c]; done.insert(p); } ans ans * ways % MOD; } ans (ans zero - 1 MOD) % MOD; cout ans \n; return 0; }5.3 代码里几个需要留心的点norm 函数里的 gcd 我是直接用了 abs 后的值这样能避免负数对 gcd 的影响。C17 的 std::gcd 对负数的行为是返回正数但保险起见我还是对 x 和 y 取了 abs。另外注意 perp 函数返回前又调了一次 norm。这一步必须做因为如果 (x,y) 约分后是 (2,4) 这种没有完全化简的值直接取垂直方向会得到 (-4,2)而 map 里存的 key 是 (1,2)根本对不上。只有在最外层统一走 norm才能保证所有 key 都是同一套规范。还有一点main 函数里 map 的遍历我用了 C17 的结构化绑定。如果你用的是 C14 或更低版本需要改成传统的迭代器方式否则编译会报错。6. 常见坑点、调试经验与复杂度分析6.1 我在实际提交中踩过的坑第一次提交 WA 的时候我整个人是懵的因为样例全部通过。后来我把生成的数据缩小手动打印 map 里的每个方向和数量才发现问题出在符号处理上。比如 (-3, 0) 这个向量我当时的 norm 函数先算出 g 3变成 (-1, 0)然后判断 x 0 整体取反得到 (1, 0)。这本身没错。但问题是另一个向量 (3, 0) 规范化后也是 (1, 0)它们应该被分到同一组。看起来好像没问题实际上问题出在我对 x 0 情况的处理上——如果某个向量是 (0, -5)我的旧代码会变成 (0, -1)然后因为没有走到 x 0 这个分支y 保持负数导致它和 (0, 5) 规范化后的 (0, 1) 被分到了两个不同的组。这就是为什么我在最终版本里单独判断了 x 0 和 y 0 的情况直接把 (0, 负数) 归一成 (0, 1)。这种边界问题只有打印中间结果才能看出来纯靠肉眼盯着代码是想不出来的。第二个坑是忘记减 1。我在计算完所有配对贡献之后直接输出 ans结果发现答案总是比标准答案大 1。后来才意识到所有配对都选择“两边都不选”时其实就是一条鱼都不抓的非法方案题目要求至少抓一条所以必须减掉这个空集。第三个坑发生在用 unordered_map 的时候。我当时为了追求常数优化直接用 unordered_mappairint,int, long long结果编译报错因为 pair 没有默认的哈希函数。手写哈希函数不是不行但这题 map 已经够快没必要把这个简单题搞复杂最后我还是换回了 map。6.2 复杂度与数据范围每个向量进入程序后做一次 gcd 约分时间复杂度是 O(log MAX(A_i, B_i))然后插入 map 是 O(log N)。整个算法的复杂度是 O(N log N)对于 N 2e5 的数据量来说非常轻松完全不用担心超时。空间方面map 里最多存 N 个方向set 里也最多存 N 个方向再加上 pow2 数组总空间消耗是 O(N)也很安全。如果你对常数极度敏感可以考虑用基数排序的思路把方向排序去重替代 map但我觉得没必要竞赛里稳定通过才是第一优先级。6.3 这题还能怎么变形如果你刷题多了会发现这种“两两冲突不能共存”的计数题本质上都是在考察你能不能找到冲突关系的数学结构。这题里冲突关系是“垂直”对应的是内积为零于是所有冲突都发生在成对的方向之间如果条件改成“平行不能共存”那么冲突就会发生在同一个方向组内部计数方式马上变成另一个样子。如果扩展到三维向量垂直方向不再是唯一的处理起来就麻烦得多。我个人在做完这题之后的体会是遇到这种抽象条件不要急着套模板先用数学语言把条件翻译一遍很多时候答案就藏在翻译的过程里。像这一步 A_i * A_j B_i * B_j 0 翻译成“垂直”整个题的复杂度瞬间从“无从下手”降到了“组合计数入门题”。最后一个实用建议如果你打算在 AtCoder 上稳定突破 ABC 的 D 题或者 E 题建议把这种“数学条件转几何意义”的题目集中刷一遍它们能帮你建立一种非常重要的敏感度——看到内积想到垂直看到叉积想到平行看到平方和想到距离。这种敏感度不是靠背模板能获得的只能靠大量实战慢慢喂出来。 
长河君 · 2026/10/13 20:16:15 · 阅读 1.2k AtCoder ABC 168 E题解析：向量内积为零的垂直冲突与组合计数
AtCoder Beginner Contest 168 的 E 题“∙ (Bullet)”一眼看上去像个物理题实际上是一道把向量几何和组合计数结合得很漂亮的题目。题目给了 N 条鱼每条鱼有两个属性 A_i 和 B_i如果两条鱼满足 A_i * A_j B_i * B_j 0就不能同时出现在渔网里问一共有多少种合法的抓鱼方案。这道题适合刚接触 AtCoder 中档题的选手也适合想复习组合计数、约分技巧和模运算经验的人它不考什么冷门算法难点全在思路转化和细节处理上。我第一次做这题时第一反应是“冲突关系能不能建图能不能用并查集”结果发现这题根本不能这样玩冲突关系不是传递的A 和 B 冲突、B 和 C 冲突不代表 A 和 C 冲突图论模型直接报废。后来老老实实把每个属性对当成向量才发现所有东西都顺了。1. 题目到底在问什么内积为零的两条鱼不能同时出现1.1 从属性对到二维向量题目给的条件是 A_i * A_j B_i * B_j 0这个式子如果你在高中认真学过向量应该一眼就能认出来这是两个二维向量 (A_i, B_i) 和 (A_j, B_j) 的内积。内积为零的几何含义就是两个向量互相垂直。所以在题意转化之后问题变成平面上有 N 个向量选一个非空子集使得子集中不存在两个互相垂直的向量问有多少种选法。这个转化是整个题的命根子。如果看不破这一点你会一直在“怎么维护这种奇怪的冲突关系”里打转看破了后面就是纯粹的统计问题。1.2 注意冲突是“垂直”不是“平行”这里有一个特别容易踩的误区很多人看到冲突条件后会把它类比成“同方向不能共存”然后按“相同或相反分成一组”来做。大错特错。方向相同或相反的向量不但能共存而且它们的内积一定不等于零。比如 (1,2) 和 (2,4) 方向相同内积是 12 24 10不冲突(1,2) 和 (-1,-2) 方向相反内积是 -1 - 4 -5也不冲突。真正冲突的是那种“一个往东一个往北”的关系。这个区别直接决定分组方式。如果是“平行不能共存”你只需要把共线的向量归成一组组内互斥但这里是“垂直不能共存”互斥关系是发生在“两个垂直方向之间”的这完全是另一套逻辑。想明白这一点之后我脑子里马上冒出一个问题方向这么多怎么把一个方向和它的垂直方向成对地找出来这就引出了下面的核心操作。2. 核心思路把 N 个向量按“方向”分组2.1 约分化简把所有向量归一化到同一个方向如果有两个向量 (2,4) 和 (1,2)它们虽然数值不同但方向完全一样。在计数时我们应该把这种方向相同的鱼放进同一个组里。最标准的做法是“规范化”也叫“归一化”先算出 g gcd(abs(x), abs(y))。把 x 和 y 同时除以 g。统一符号让第一个非零分量为正。举个例子(2,4) → 除以 gcd 2 → (1,2)(-2,-4) → 除以 gcd 2 → (-1,-2)然后第一个非零分量是负数整体取反变成 (1,2)(-2,4) → 除以 gcd 2 → (-1,2)第一个非零分量已经是负数保留 (-1,2)这样做完之后所有方向相同的向量都会变成同一个 pair直接扔进 map 里统计个数就行。这里有个小细节必须先处理掉如果一个向量是 (0,0)它没法规范化需要单独挑出来。因为它和任何向量的内积都是 0所以它是一个超级冲突源后面要特殊对待。还有一种边界情况是 x0 或 y0。比如 (0,-3)如果直接除以 gcd 会得到 (0,-1)然后因为第一个非零分量是 y此时 y-1 是负数需要把 y 取反变成 (0,1)。我在写 norm 函数时习惯先把 x0 的情况单独返回 (0,1)把 y0 的情况单独返回 (1,0)省得后面符号判断出问题。2.2 用 pair 作为 map 的 key规范化之后每个非零向量都变成了一个 pairint, int。我选用了 mappairint,int, long long 来统计每个方向的个数。为什么不直接用 unordered_map因为 pair 不是内置哈希类型用 unordered_map 需要手写哈希函数比较麻烦。这题 N 最多 2e5map 的 O(log N) 插入复杂度完全够用所以直接用 map 是最省心的选择。这一段统计代码看起来就是mappairint,int, long long cnt; long long zero 0; for (int i 0; i N; i) { long long a, b; cin a b; if (a 0 b 0) { zero; continue; } cnt[norm(a, b)]; }到这里我们已经把一个看似复杂的向量集合压缩成了若干个“方向桶”每个桶里有若干条鱼。剩下的问题就是这些方向桶之间哪些是互斥的哪些是独立的。3. 互斥配对与组合计数推导3.1 每个方向都有且只有一个“垂直方向”对于一个非零方向 (x, y)所有与它垂直的向量方向是 (y, -x) 的方向也就是 (-y, x)。举个例子就清楚了方向 (1,2)垂直方向是 (-2,1)。方向 (-1,2)垂直方向是 (-2,-1)这个向量规范化之后是 (2,1)。注意垂直方向也要做同样的规范化处理。也就是说如果 map 里存的是规范化之后的 pair那么找某个方向的垂直方向必须用规范化之后的 pair 去找否则会因为符号或者约分不一致而找不到。我封装了一个函数pairint,int perp(pairint,int p) { return norm(-p.second, p.first); }这样只要 p 是规范化过的perp(p) 也一定是规范化过的。现在所有非零方向都形成了一个一个的“配对”一个方向 p 和它的垂直方向 q 是互斥的。3.2 一个配对内的贡献怎么算假设方向 p 上有 cnt[p] 条鱼方向 q 上有 cnt[q] 条鱼。这两个方向的鱼不能同时选那么合法的选择有三种互斥情况只从 p 里选鱼从 cnt[p] 条鱼中选一个非空子集方案数是 2^{cnt[p]} - 1。只从 q 里选鱼从 cnt[q] 条鱼中选一个非空子集方案数是 2^{cnt[q]} - 1。p 和 q 都不选只有 1 种方案。把三种情况加起来得到这一个配对对答案的贡献是2^{cnt[p]} 2^{cnt[q]} - 1这里要特别提醒一下为什么不用乘法而用加法。因为这两个方向的鱼是互斥的你选了 p 方向的任何一条鱼就绝对不能选 q 方向的任何一条鱼反之亦然。互斥事件之间应该用加法原理而不是乘法原理。大多数第一次做这道题的人在这里会天然地写出乘法然后样例都过不了整个人开始怀疑人生。其实只要想清楚“p 选了 q 就不能选”这个约束就不会搞混。3.3 没有垂直方向的组怎么处理如果某个方向 p 的垂直方向 perp(p) 在 map 里根本不存在说明输入数据里没有任何一条鱼的属性在 p 的垂直方向上。那么 p 方向上的鱼就没有任何“天敌”它们可以随便选也可以不选。这种情况下贡献就是简单的 2^{cnt[p]}。你可能会觉得这没什么好说的但我第一次写的时候真的忘了这个分支结果样例都过得不完整。后来在调试时发现有一类方向的 cnt 一直没被计算进去才反应过来。处理整个配对的计算逻辑可以这样写setpairint,int done; long long ans 1; for (auto [p, c] : cnt) { if (done.count(p)) continue; auto q perp(p); long long ways; if (cnt.count(q)) { long long c1 c; long long c2 cnt[q]; ways (pow2[c1] pow2[c2] - 1 MOD) % MOD; done.insert(p); done.insert(q); } else { ways pow2[c]; done.insert(p); } ans ans * ways % MOD; }使用 done 集合的原因很简单避免同一个配对被算两次。比如 p 的垂直方向是 qq 的垂直方向必然又是 p当 for 循环遍历到 q 时如果不去重就会又把 p 和 q 这个配对算一遍答案就错了。4. 零向量和答案的最终拼装4.1 零向量是“超级冲突源”现在回到那个我们一开始就单独挑出来的 (0,0)。(0,0) 和任何向量的内积都是 0所以它和所有鱼都冲突。同时两条零向量之间也冲突因为 (0,0) 和 (0,0) 的内积也是 0。这意味着什么意味着你最多只能选一条零向量而且一旦选了零向量其他任何鱼都不能选。从计数角度来说假设有 zero 条零向量它们能提供的“新方案”其实只有 zero 种单独选第一条、单独选第二条、……、单独选第 zero 条。剩下还有一种“零向量一条都不选”的情况这个不需要单独加因为它已经被包含在“非零向量部分选法”的空集情况里了。4.2 把所有贡献组装起来现在你手里有两部分答案非零向量部分按前面第 3 章的配对方式相乘得到一个值 ans注意这个值里包含“非零部分一条都不选”的空集方案。零向量部分提供了 zero 种“只选一条零向量”的方案。但是题目要求非空集合。非零部分算出来的 ans 里包含的空集方案需要被减掉。所以最终答案是ans (ans zero - 1 MOD) % MOD;这里有一个很容易让人困惑的地方为什么不是 ans * (zero 1)因为零向量和其他任何向量都冲突它在逻辑上不是“每个方向组都可以独立选择”的关系而是一个“要么选一条零向量要么完全忽略零向量”的整体约束。如果非零部分已经选了至少一条鱼那么零向量必须一个都不选只有非零部分为空集时才允许去选那唯一一条零向量。用乘法会错误地允许“非零部分选着零向量也选着”的情况答案直接起飞。这道题 AC 代码的精华就在这里那一个减法。5. 完整代码与实现细节5.1 预处理 2 的幂代码里要多次用到 2^{cnt}而且 cnt 最大到 2e5所以我先预处理 pow2 数组vectorlong long pow2(N 1); pow2[0] 1; for (int i 1; i N; i) { pow2[i] pow2[i - 1] * 2 % MOD; }这样后面直接查表就行没必要做快速幂。5.2 C17 完整实现下面是我提交时用的完整代码加了注释#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; pairint,int norm(int x, int y) { if (x 0 y 0) return {0, 0}; if (x 0) return {0, 1}; if (y 0) return {1, 0}; int g gcd(abs(x), abs(y)); x / g; y / g; // 统一符号让第一个非零分量为正 if (x 0) { x -x; y -y; } else if (x 0 y 0) { y -y; } return {x, y}; } pairint,int perp(pairint,int p) { return norm(-p.second, p.first); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; mappairint,int, long long cnt; long long zero 0; for (int i 0; i N; i) { int a, b; cin a b; if (a 0 b 0) { zero; continue; } cnt[norm(a, b)]; } vectorlong long pow2(N 1); pow2[0] 1; for (int i 1; i N; i) { pow2[i] pow2[i - 1] * 2 % MOD; } setpairint,int done; long long ans 1; for (auto [p, c] : cnt) { if (done.count(p)) continue; auto q perp(p); long long ways; if (cnt.count(q)) { long long c1 c; long long c2 cnt[q]; ways (pow2[c1] pow2[c2] - 1 MOD) % MOD; done.insert(p); done.insert(q); } else { ways pow2[c]; done.insert(p); } ans ans * ways % MOD; } ans (ans zero - 1 MOD) % MOD; cout ans \n; return 0; }5.3 代码里几个需要留心的点norm 函数里的 gcd 我是直接用了 abs 后的值这样能避免负数对 gcd 的影响。C17 的 std::gcd 对负数的行为是返回正数但保险起见我还是对 x 和 y 取了 abs。另外注意 perp 函数返回前又调了一次 norm。这一步必须做因为如果 (x,y) 约分后是 (2,4) 这种没有完全化简的值直接取垂直方向会得到 (-4,2)而 map 里存的 key 是 (1,2)根本对不上。只有在最外层统一走 norm才能保证所有 key 都是同一套规范。还有一点main 函数里 map 的遍历我用了 C17 的结构化绑定。如果你用的是 C14 或更低版本需要改成传统的迭代器方式否则编译会报错。6. 常见坑点、调试经验与复杂度分析6.1 我在实际提交中踩过的坑第一次提交 WA 的时候我整个人是懵的因为样例全部通过。后来我把生成的数据缩小手动打印 map 里的每个方向和数量才发现问题出在符号处理上。比如 (-3, 0) 这个向量我当时的 norm 函数先算出 g 3变成 (-1, 0)然后判断 x 0 整体取反得到 (1, 0)。这本身没错。但问题是另一个向量 (3, 0) 规范化后也是 (1, 0)它们应该被分到同一组。看起来好像没问题实际上问题出在我对 x 0 情况的处理上——如果某个向量是 (0, -5)我的旧代码会变成 (0, -1)然后因为没有走到 x 0 这个分支y 保持负数导致它和 (0, 5) 规范化后的 (0, 1) 被分到了两个不同的组。这就是为什么我在最终版本里单独判断了 x 0 和 y 0 的情况直接把 (0, 负数) 归一成 (0, 1)。这种边界问题只有打印中间结果才能看出来纯靠肉眼盯着代码是想不出来的。第二个坑是忘记减 1。我在计算完所有配对贡献之后直接输出 ans结果发现答案总是比标准答案大 1。后来才意识到所有配对都选择“两边都不选”时其实就是一条鱼都不抓的非法方案题目要求至少抓一条所以必须减掉这个空集。第三个坑发生在用 unordered_map 的时候。我当时为了追求常数优化直接用 unordered_mappairint,int, long long结果编译报错因为 pair 没有默认的哈希函数。手写哈希函数不是不行但这题 map 已经够快没必要把这个简单题搞复杂最后我还是换回了 map。6.2 复杂度与数据范围每个向量进入程序后做一次 gcd 约分时间复杂度是 O(log MAX(A_i, B_i))然后插入 map 是 O(log N)。整个算法的复杂度是 O(N log N)对于 N 2e5 的数据量来说非常轻松完全不用担心超时。空间方面map 里最多存 N 个方向set 里也最多存 N 个方向再加上 pow2 数组总空间消耗是 O(N)也很安全。如果你对常数极度敏感可以考虑用基数排序的思路把方向排序去重替代 map但我觉得没必要竞赛里稳定通过才是第一优先级。6.3 这题还能怎么变形如果你刷题多了会发现这种“两两冲突不能共存”的计数题本质上都是在考察你能不能找到冲突关系的数学结构。这题里冲突关系是“垂直”对应的是内积为零于是所有冲突都发生在成对的方向之间如果条件改成“平行不能共存”那么冲突就会发生在同一个方向组内部计数方式马上变成另一个样子。如果扩展到三维向量垂直方向不再是唯一的处理起来就麻烦得多。我个人在做完这题之后的体会是遇到这种抽象条件不要急着套模板先用数学语言把条件翻译一遍很多时候答案就藏在翻译的过程里。像这一步 A_i * A_j B_i * B_j 0 翻译成“垂直”整个题的复杂度瞬间从“无从下手”降到了“组合计数入门题”。最后一个实用建议如果你打算在 AtCoder 上稳定突破 ABC 的 D 题或者 E 题建议把这种“数学条件转几何意义”的题目集中刷一遍它们能帮你建立一种非常重要的敏感度——看到内积想到垂直看到叉积想到平行看到平方和想到距离。这种敏感度不是靠背模板能获得的只能靠大量实战慢慢喂出来。