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作为键遇到 a0 的情况要么除零要么特判处理起来很丑。所以正确做法是把向量约分成最简整数对。比如 (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 也要再过一次 normdef 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。方案是选第一条零向量或者选第二条零向量。如果代码里把零向量也塞进 Countergcd(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^97质数直接 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^pcpc 0 时整体变成 2^c这正好符合预期。不要在代码里为了“省一次 pow”去特判 pc 0那样反而容易写错。5. 赛后的一点体会这道题最值得记下来的不是公式本身而是“把垂直关系看成图”的那个视角。很多组合计数题一开始看起来像是在考数据结构实际上是在考你能不能把一个计数条件转化成干净的图结构。非零向量的垂直关系之所以能变成 K2 分组是因为每个方向只有一个垂直方向零向量之所以要单独处理是因为它和所有方向都有边。想明白了这两点后面的公式就是水到渠成。我在比赛里栽的第一个跟头就是符号统一。当时我只约了最大公约数没有翻转符号(1,1) 和 (-1,-1) 各成一个方向桶结果一对互斥方向变成了四向互斥公式怎么算都不对。后来我把垂直关系画在纸上才发现这两个方向必须合并。第二个跟头是零向量的计数。第一次我把 z 直接加到 total 上然后减 1当时觉得“多选一条零向量只是多了一种方案”完全忽略了选零向量时其他所有鱼都不能选的问题。后面自己构造了好几个含零向量的样例才把公式修正成现在这样。如果你也卡在这道题上我建议先自己把所有方向画出来认真做一次符号统一再拿我上面的三个测试用例去验证。把零向量的处理想清楚之后这道题的难度其实一下子降下来了。
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作为键遇到 a0 的情况要么除零要么特判处理起来很丑。所以正确做法是把向量约分成最简整数对。比如 (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 也要再过一次 normdef 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。方案是选第一条零向量或者选第二条零向量。如果代码里把零向量也塞进 Countergcd(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^97质数直接 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^pcpc 0 时整体变成 2^c这正好符合预期。不要在代码里为了“省一次 pow”去特判 pc 0那样反而容易写错。5. 赛后的一点体会这道题最值得记下来的不是公式本身而是“把垂直关系看成图”的那个视角。很多组合计数题一开始看起来像是在考数据结构实际上是在考你能不能把一个计数条件转化成干净的图结构。非零向量的垂直关系之所以能变成 K2 分组是因为每个方向只有一个垂直方向零向量之所以要单独处理是因为它和所有方向都有边。想明白了这两点后面的公式就是水到渠成。我在比赛里栽的第一个跟头就是符号统一。当时我只约了最大公约数没有翻转符号(1,1) 和 (-1,-1) 各成一个方向桶结果一对互斥方向变成了四向互斥公式怎么算都不对。后来我把垂直关系画在纸上才发现这两个方向必须合并。第二个跟头是零向量的计数。第一次我把 z 直接加到 total 上然后减 1当时觉得“多选一条零向量只是多了一种方案”完全忽略了选零向量时其他所有鱼都不能选的问题。后面自己构造了好几个含零向量的样例才把公式修正成现在这样。如果你也卡在这道题上我建议先自己把所有方向画出来认真做一次符号统一再拿我上面的三个测试用例去验证。把零向量的处理想清楚之后这道题的难度其实一下子降下来了。
