P16643 [GKS 2018 #B] King's Circle

在 Kickstartia 王国，人们记忆所及以来，第一次到处洋溢着庆祝的气氛：新国王的加冕日到了。按照加冕仪式的惯例，皇家游行队伍将穿过首都的街道。 首都可以看作是一个无限的二维平面，其中有无穷多条无限长的街道，相互间隔 1 米，水平方向和垂直方向贯穿整个平面。水平街道从上到下用从负无穷到正无穷的整数标记，垂直街道从左到右也用从负无穷到正无穷的整数标记。 首都有 $N$ 家咖啡馆，第 $i$ 家位于垂直街道 $V_i$ 与水平街道 $H_i$ 的交汇处。没有两家咖啡馆位于同一交叉口。为了让游行技术人员感到满意且吃饱喝足，你将恰好选择三家咖啡馆，供他们在途中停留。 为了在混乱中引入一些秩序，你额外决定游行必须从起点回到终点，并且其路径必须形成一个正方形（直边，所有边长相等）。咖啡馆可以位于正方形的任意位置（边上或角上）。 这立即带来了一个问题：根据你选择的三家咖啡馆，可能无法构造出一个经过这三家咖啡馆的正方形游行路线。因此，你的任务是找出：有多少个不同的三家咖啡馆的集合，使得至少存在一个包含该集合中全部三家咖啡馆的正方形游行路线？（两个集合不同当且仅当其中一个包含另一个所没有的咖啡馆。）

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行包含十个整数组成：$N$、$V_1$、$H_1$、$A$、$B$、$C$、$D$、$E$、$F$ 和 $M$。 $N$ 是咖啡馆的数量。第一家咖啡馆位于垂直街道 $V_1$ 与水平街道 $H_1$ 的交汇处。 剩余咖啡馆的位置 $V_i$、$H_i$（$i = 2$ 到 $N$）可按如下方式生成： * $V_i = (A \times V_{i-1} + B \times H_{i-1} + C) \bmod M$ * $H_i = (D \times V_{i-1} + E \times H_{i-1} + F) \bmod M$

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是满足上述条件的咖啡馆集合的数量。

在样例 #1 中，有四家咖啡馆，分别位于 $(1, 1)$、$(1, 0)$、$(0, 3)$ 和 $(4, 0)$。如图所示，存在正方形游行路线经过以下咖啡馆集合：$(1, 1)$、$(1, 0)$、$(0, 3)$；或 $(1, 1)$、$(1, 0)$、$(4, 0)$；或 $(1, 0)$、$(0, 3)$、$(4, 0)$。不存在经过 $(1, 1)$、$(0, 3)$、$(4, 0)$ 这三个咖啡馆的正方形游行路线。 :::align{center}  ::: 在样例 #2 中，有 $6$ 家咖啡馆，分别位于 $(3, 1)$、$(4, 1)$、$(5, 1)$、$(6, 1)$、$(7, 1)$ 和 $(8, 1)$。由于它们都在同一条垂直街道上，任意三个咖啡馆都存在经过它们的正方形游行路线。因此答案为 $\binom{6}{3} = 20$。 在样例 #3 中，有 $3$ 家咖啡馆，分别位于 $(7, 24)$、$(19, 17)$、$(0, 34)$。不存在经过这三家咖啡馆的正方形游行路线，因此答案为 $0$。 **注意：** 对于本题的大数据集，我们不建议使用解释型/较慢的语言。 ### 限制条件 $1 \le T \le 100$。 $0 \le A < M$。 $0 \le B < M$。 $0 \le C < M$。 $0 \le D < M$。 $0 \le E < M$。 $0 \le F < M$。 $0 \le V_1 < M$。 $0 \le H_1 < M$。 对于所有 $i \neq j$，$(V_i, H_i) \neq (V_j, H_j)$。 **小数据集（测试集 1 – 可见）** $3 \le N \le 1000$。 $2 \le M \le 1000$。 **大数据集（测试集 2 – 隐藏）** $3 \le N \le 5 \times 10^5$。 $2 \le M \le 10^6$。 翻译由 DeepSeek V4 Pro 完成