企业官网建设流程全解析

ABC168 的 E 题《(Bullet)》是我刷 Beginner 场以来少有的、在“数学建模那一步”卡住我的题。题干就一句话：N 条沙丁鱼，每条有一个向量 (A_i, B_i)，两条鱼不能同时进篮子，当且仅当它们的点积为零。第一次读下去，感觉连数据结构都不用，但真动手算的时候才发现，它考的是方向空间里的分组计数，后面的组合公式反而比题意本身更绕。这篇题解会把从“题意翻译”到“公式推导”再到 Python 实现 的完整链路拆开写，特别是我在零向量和垂直配对计数上踩过的坑。如果你正在补 ABC168，或者想复习一下 “哈希分组 + 乘法原理” 这类套路，可以对照着看。

1. 题意拆解：点积为零在选鱼问题里到底是什么

1.1 题面很短，但是信息密度很大

题目给的是 N 条沙丁鱼，每条对应 (A_i, B_i)。要求选一个非空子集，使得子集中任意两条的点积都不等于 0。点积公式是 A*A' + B*B'。这个条件翻译成几何语言就是两条向量垂直。

举个具体例子：假设选了 (1,0) 和 (0,1)，点积是 1*0 + 0*1 = 0，所以这两条不能同时选。但如果选 (1,0) 和 (1,1)，点积是 1*1 + 0*1 = 1，可以同时选。换句话说，我们需要在所有 N 条向量组成的集合里，找到一个不含“垂直对”的非空子集，问方案数。

这里要注意一个容易忽略的点：题目的限制是“任意两条垂直就不能同时选”，而不是“和某条基准向量垂直”。所以如果向量之间形成复杂的垂直关系网，计数会变麻烦。好在后面我们会看到，非零向量的垂直关系其实非常“干净”，根本没机会形成复杂的关系网。

1.2 用斜率替代方向：为什么必须用约分后的整数对

我见过不少人拿到这题第一反应是：把每个向量化成斜率，然后统计斜率。这个思路方向是对的，但直接用浮点数存斜率会死得很惨。

原因有两点。第一，A_i 和 B_i 的绝对值可以达到 10^18 量级，两个不同方向可能只差一个极小的角度，斜率差值远小于 double 的精度。double 能精确表示的整数大约到 2^53，也就是 9e15 左右，10^18 的数字在做运算时精度已经不够了。第二，垂直方向有一条是竖直线，斜率无穷大，如果你在代码里用b / a作为键，遇到 a=0 的情况要么除零，要么特判，处理起来很丑。

所以正确做法是：把向量约分成最简整数对。比如 (2,2) 和 (3,3) 都归一化成 (1,1)，(4,-6) 归一化成 (2,-3)。这样既没有精度问题，又天然把相同方向的所有向量合并到了一起。

这里还有一个比“约分”更关键的操作：统一符号。如果不统一符号，(1,1) 和 (-1,-1) 会被当成两个不同的方向桶，但实际上它们在计数上是等价的。为什么等价？因为 (1,1) 的垂直方向是 (1,-1)（或者说 (-1,1)），(-1,-1) 的垂直方向也是 (1,-1) 和 (-1,1)。如果你把 (1,1) 和 (-1,-1) 拆成两个桶，会发现它们的“互斥关系”不是一对一，而是一对多，公式就没法用了。反过来，如果把它们合并成一个桶，所有 (1,1)、(-1,-1) 内部的向量之间点积不为 0，可以任意组合，合并后的“方向对”结构才成立。所以符号统一这一步不是锦上添花，而是整个模型成立的前提。

2. 标准化方向：从向量到桶的映射

2.1 一个不会产生精度问题的 normalize

统一的标准化函数长这样：

import math def norm(a, b): g = math.gcd(abs(a), abs(b)) a //= g b //= g if a < 0 or (a == 0 and b < 0): a = -a b = -b return (a, b)

这个函数做的事很简单：先约掉最大公约数，然后把方向翻到“标准状态”。标准状态我选的是“第一个非零分量必须为正”。如果第一个非零分量是 x 就要求 x > 0；如果 x == 0，那就要求 y > 0。

举个例子：(3,-4) 保持 (3,-4)；(-3,4) 翻成 (3,-4)；(0,-5) 翻成 (0,5)。这样任意方向只有一个唯一的 key。

注意：norm(0, 0)是没有意义的，因为 gcd(0,0) 在数学上未定义，代码里会直接除零报错。所以零向量必须在调用 norm 之前单独拎出来统计。

2.2 垂直方向的查找与 pair 的唯一化

有了方向桶之后，下一步要处理垂直关系。给定一个非零方向 (a,b)，它的垂直方向是 (-b,a)。为什么要这样？因为 (a,b) 和 (-b,a) 的点积是 a*(-b) + b*a = 0，这正好是垂直关系。

但要注意，(-b,a) 的符号不一定满足标准化规则，所以垂直方向的 key 也要再过一次 norm：

def perp_key(d): a, b = d return norm(-b, a)

举个例子，方向 (1,1) 的垂直方向是 (-1,1)，norm 后变成 (1,-1)。方向 (1,-1) 的垂直方向是 (1,1)。所以 (1,1) 和 (1,-1) 构成一对互斥方向。方向 (2,-1) 的垂直方向是 (1,2)，norm 后保持 (1,2)。

如果把每个方向看成一个点，点与点之间连一条“互斥线”，那非零向量形成的图就是一堆互不连通的线段，每条线段只有两个端点。我把它叫作 K2 分组，这个结构是整个计数公式的地基。

2.3 为什么“方向对”结构是一堆互不相交的K2

很多人第一次看到这里会问：那方向 (1,1) 会不会既和 (1,-1) 垂直，又和 (-1,1) 垂直？从向量几何的角度看，(1,1) 确实和 (-1,1) 垂直，也和 (1,-1) 垂直，这不就形成“三角关系”了吗？

关键在于：我们做符号统一之后，(-1,1) 和 (1,-1) 被归一成了同一个方向桶。所以 (1,1) 的互斥对象只有一个桶，就是 (1,-1)。同理，(-1,-1) 归一成 (1,1)，它的互斥对象也是 (1,-1)。也就是说，原来的 4 个方向 ((1,1)、(-1,-1)、(1,-1)、(-1,1)) 在标准化之后压缩成了 2 个桶，互斥关系变成了一对一。这就是为什么必须统一符号。

从数学上严格说，非零方向向量 d 的垂直方向 d⊥ 只有一个，垂直关系是自反且对称的：如果 d⊥ = e，那么 e⊥ = d。所以方向图由若干条互不相交的边构成。一个方向桶只会和一个垂直方向桶绑定在一起，不会出现“三角形”或“星形”。除了零向量，零向量是唯一的例外，它和所有方向都垂直，后面单独处理。

3. 计数公式的完整推导

3.1 先算“允许空集”的总方案数

假设存在一对互斥方向 (X, Y)，X 方向桶里有 a 条鱼，Y 方向桶里有 b 条鱼。这一对方向对整体方案的贡献是多少？

X 方向里的鱼可以任意选择，包括空集和所有非空子集，共 2^a 种选法。Y 方向同理，共 2^b 种选法。但 X 和 Y 不能同时选非空子集，所以：

• 只从 X 方向选：2^a 种（包含空集）
• 只从 Y 方向选：2^b 种（包含空集）
• 空集被算了两次，需要减掉 1

所以这一对互斥方向的贡献就是 2^a + 2^b - 1。

这里的“空集”非常重要，因为我们要先用乘法原理把每个方向对的独立选择乘起来，最后再统一减去空集。如果不保留空集，后面的乘法会乱套。

把所有这些独立方向对的贡献乘起来，得到一个包含空集在内的方案数：

total = ∏ (2^{a_i} + 2^{b_i} - 1)

其中 a_i、b_i 属于同一对互斥方向桶的鱼个数。如果某个方向的垂直方向不存在鱼，那 b_i = 0，对应的那一项就是 2^{a_i} + 2^0 - 1 = 2^{a_i}，含义是：这个方向桶可以随便选或不选，没有约束。

为什么不同方向对之间可以直接相乘？因为任意两条鱼只要不在同一个“垂直对”里，它们的点积就不为 0，不会互相干扰。举例来说，(1,1) 这条鱼和 (2,-1) 这条鱼点积是 1，合法；和 (1,0) 这条鱼点积是 1，合法。跨方向对的组合都是安全的。

3.2 零向量：唯一的例外

零向量 (0,0) 是非常特殊的存在，它和任何向量的点积都是 0。也就是说，一条零向量会和所有非零向量互斥，也会和其他零向量互斥。

这下不能把零向量放进上面任何一个方向对了。如果我们强行把 (0,0) 标准化，整个模型就崩了。假设有 z 条零向量：

• 方案里如果不选零向量，那就走上面的 total 路线，允许空集。
• 方案里如果选零向量，那只能选一条，且其他所有非零向量都不能选。所以这类方案恰好有 z 种。

因此最终答案非空方案数 = (total - 1) + z。减 1 是为了去掉整体方案里的那个空集，加 z 是把“恰好选一条零向量”的方案数补回来。

踩坑提示：千万不要写成 total * z 或者 (total - 1) * z。选零向量时非零向量一个都不能选，所以 z 种方案是彼此独立的，没有和其他方向对进行组合的余地。

3.3 从总方案到答案：一个具体的数值例子

写一个我自己验证过的小例子。输入：

3 2 2 -1 -1 1 -1

(2,2) 归一成 (1,1)，(-1,-1) 也归一成 (1,1)，所以 (1,1) 方向桶里有 2 条鱼。(1,-1) 方向桶里有 1 条鱼。这一对垂直方向贡献是 2^2 + 2^1 - 1 = 5。total = 5，去掉空集后非空方案数 = 4。

这 4 种方案分别是：选 (1,1) 方向的一条、选 (1,1) 方向的另一条、选两条 (1,1)、选 (1,-1) 方向的一条。(1,1) 方向和 (1,-1) 方向不能同时选，所以不能出现跨方向的方案。看起来符合直觉。

再加两条零向量测试：

4 0 0 0 0 1 0 0 1

(1,0) 和 (0,1) 是一对垂直方向，t = (1,0) 方向 1 条 + (0,1) 方向 1 条，贡献 = 2 + 2 - 1 = 3。z = 2。答案 = 3 - 1 + 2 = 4。合法方案：选一条零向量（2 种）、选 (1,0)（1 种）、选 (0,1)（1 种），外加空集排除，正好 4 种。

4. 完整实现与细节坑

4.1 可以直接抄作业的 Python 代码

import sys import math from collections import Counter MOD = 10**9 + 7 def norm(a, b): g = math.gcd(abs(a), abs(b)) a //= g b //= g if a < 0 or (a == 0 and b < 0): a = -a b = -b return (a, b) def perp_key(d): a, b = d return norm(-b, a) def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) zero = 0 cnt = Counter() idx = 1 for _ in range(n): a = int(data[idx]) b = int(data[idx + 1]) idx += 2 if a == 0 and b == 0: zero += 1 continue cnt[norm(a, b)] += 1 visited = set() ans = 1 for d, c in cnt.items(): p = perp_key(d) pair = (min(d, p), max(d, p)) if pair in visited: continue visited.add(pair) pc = cnt.get(p, 0) ans = ans * (pow(2, c, MOD) + pow(2, pc, MOD) - 1) % MOD ans = (ans - 1 + zero) % MOD print(ans) if __name__ == "__main__": main()

代码里比较核心的是visited这个集合。因为方向和它的垂直方向在遍历时都会被访问到，如果不去重，一个互斥对会被计算两次。用min(d, p), max(d, p)构造一个有序的 pair，就可以保证同一个互斥对只被处理一次。

4.2 三个容易翻车的测试用例

我自己提交的时候就是在这三个地方连续翻车，写出来给大家避坑。

第一个用例，纯零向量：

2 0 0 0 0

正确答案是 2。方案是选第一条零向量或者选第二条零向量。如果代码里把零向量也塞进 Counter，gcd(0,0) 直接抛异常。

第二个用例，部分零向量：

4 0 0 0 0 1 0 0 1

上面推导过答案是 4。这个用例专门用来验证ans - 1 + zero的顺序。如果你先加 zero 再减 1，结果也是 4，看起来没问题，但在更大数据里可能出现负数取模错误。统一用(ans - 1 + zero) % MOD最稳。

第三个用例，同一个方向出现多次但垂直方向缺失：

3 1 0 1 0 2 0

所有向量都归一成 (1,0)，垂直方向 (0,1) 没有鱼，所以贡献是 2^3 + 2^0 - 1 = 8，减掉空集后答案 = 7。这也是正确的：因为三条鱼之间点积都不为 0，任意非空子集全合法，非空子集数就是 2^3 - 1 = 7。

4.3 模运算与性能注意事项

模数是 10^9+7，质数，直接 pow 就行。N 最大 2e5，每个方向桶至多算一次 pow，复杂度完全没问题。总复杂度是 O(N log C)，其中 C 是 A_i、B_i 的绝对值范围，gcd 的 log 因子在这里可以忽略。

性能方面值得注意的一点是输入读取。N = 2e5 时用sys.stdin.readline也够快，但我习惯直接buffer.read().split()，一次把全部数字读进来再切片，能省掉 Python 的逐行 IO 开销。在 AtCoder 这种 2 秒时限的题上，IO 优化通常不是必需品，但能省一点是一点。

还有一个小的变量名陷阱：代码里cnt.get(p, 0)在 p 不存在时返回 0，但在数学上这一项是 2^pc，pc = 0 时整体变成 2^c，这正好符合预期。不要在代码里为了“省一次 pow”去特判 pc == 0，那样反而容易写错。

5. 赛后的一点体会

这道题最值得记下来的不是公式本身，而是“把垂直关系看成图”的那个视角。很多组合计数题一开始看起来像是在考数据结构，实际上是在考你能不能把一个计数条件转化成干净的图结构。非零向量的垂直关系之所以能变成 K2 分组，是因为每个方向只有一个垂直方向；零向量之所以要单独处理，是因为它和所有方向都有边。想明白了这两点，后面的公式就是水到渠成。

我在比赛里栽的第一个跟头就是符号统一。当时我只约了最大公约数，没有翻转符号，(1,1) 和 (-1,-1) 各成一个方向桶，结果一对互斥方向变成了四向互斥，公式怎么算都不对。后来我把垂直关系画在纸上，才发现这两个方向必须合并。

第二个跟头是零向量的计数。第一次我把 z 直接加到 total 上，然后减 1，当时觉得“多选一条零向量只是多了一种方案”，完全忽略了选零向量时其他所有鱼都不能选的问题。后面自己构造了好几个含零向量的样例，才把公式修正成现在这样。

如果你也卡在这道题上，我建议先自己把所有方向画出来，认真做一次符号统一，再拿我上面的三个测试用例去验证。把零向量的处理想清楚之后，这道题的难度其实一下子降下来了。