H. Tower Capturing 详细题解

题目重述

平面上有 $n$ 个互不相同的点（塔），任意三点不共线，任意四点不共圆。初始时你拥有 $1$ 号和 $2$ 号点。每次操作可以选择两个你已拥有的点 $P,Q$ 和一个未拥有的点 $R$，使得过 $P,Q,R$ 三点的圆包含所有 $n$ 个点（即所有点都在该圆内部或边界上）。然后你可以占领三角形 $\triangle PQR$ 内部及边界上的所有点（包括 $R$）。问：最短的操作序列有多少种（仅考虑每次选择的 $R$，不考虑 $P,Q$ 的选择，因为 $P,Q$ 可由 $R$ 唯一确定？题目说明：两个计划如果 $R$ 的序列相同就算相同，不管 $P,Q$ 如何）。如果不可能占领所有点，输出 $0$，结果对 $998244353$ 取模。

核心观察

1. 操作的本质：当圆通过 $P,Q,R$ 且包含所有点时，该圆实际上是整个点集的最小外接圆吗？不一定，但条件很强：所有点都在圆内。这意味着 $P,Q,R$ 必须构成一个“大”圆，使得所有点都落在其内部。实际上，由于无四点共圆，这样的三元组是稀少的。更关键的是，一旦满足条件，三角形 $\triangle PQR$ 内包含的点集是确定的（由几何关系决定）。而且，操作允许你一次性占领这些点。

2. 状态表示：用一个 $n$ 位的二进制掩码（bitset）表示当前已拥有的点集。初始状态为只有点 $1$ 和 $2$。目标状态为全 $1$。

3. 操作的可逆性：从状态 $S$ 出发，若存在一个三元组 $(P,Q,R)$ 满足 $P,Q\in S$，$R\notin S$，且过 $P,Q,R$ 的圆包含所有点，则操作后新状态为 $S \cup T$，其中 $T$ 是三角形 $\triangle PQR$ 内部及边界上的所有点（包括 $R$）。注意 $T$ 可能包含多个点。

4. 最短路径问题：我们要求从初始状态到全状态的最短操作次数，并且统计达到该最短长度的不同操作序列的数量（序列由每次选择的 $R$ 构成，$P,Q$ 可任意，但序列中 $R$ 的顺序决定了操作序列）。由于 $n\le 100$，$n$ 的总和 $\le 1000$，可以用 BFS 在状态空间上搜索。状态数最多 $2^{100}$ 太大，但实际可达状态数远小于此，因为每次操作至少增加一个点，且 $n$ 很小，BFS 深度最多 $n-2$。但由于 $n$ 最大 $100$，直接 BFS 仍可能状态爆炸。不过题目限制 $n$ 总和 $\le 1000$，且实际数据中 $n$ 较小，BFS 可以接受（代码中使用 bitset 和 unordered_map）。

算法步骤

1. 预处理所有可能的三元组
   枚举所有 $C(n,3)$ 个三元组 $(i,j,k)$。对于每个三元组，检查过这三点的圆是否包含所有其他点（即剩余 $n-3$ 个点都在圆内或圆上）。由于无四点共圆，不会有点恰在圆上，所以只需严格内部判断。
   若满足，则计算三角形 $\triangle (i,j,k)$ 内部及边界上的点集（包括三个顶点）。因为任意三点不共线，三角形内部点可以用叉积符号判断（点在三角形内当且仅当三个重心坐标的叉积同号，或边界为零）。得到该三元组对应的“占领点集” $mask$（bitset）。

2. BFS 搜索

   • 初始状态：start 包含点 $0$ 和 $1$（因为输入顺序，索引从 $0$ 开始）。
   • 目标状态：target 包含所有 $n$ 个点。
   • 使用队列 queue<bitset> 进行 BFS，同时记录每个状态的距离 dist 和方案数 ways（模 $998244353$）。
   • 从当前状态 $cur$ 出发，枚举所有预处理的 $(i,j,k)$ 三元组。如果 $i,j,k$ 中恰好有两个点在 $cur$ 中（即 $P,Q$ 已拥有），且第三个点 $R$ 不在 $cur$ 中，则操作合法。将 $cur$ 与对应的占领点集取并集得到新状态 $nxt$。
   • 如果 $nxt$ 未被访问过，则设置 dist[nxt]=dist[cur]+1，ways[nxt]=ways[cur]，并加入队列。
   • 如果 $nxt$ 已经访问过且距离等于当前距离加 $1$，则累加方案数 ways[nxt] += ways[cur]。
   • BFS 保证第一次到达目标状态时的距离即为最短长度，且累加方案数即为最短长度的方案数。

3. 输出结果
   如果 BFS 结束后未到达目标状态，输出 $0$；否则输出 ways[target]。

正确性证明

• 操作等价性：每次操作中，$P,Q$ 必须已拥有，$R$ 未拥有，且圆包含所有点。题目中 $P,Q$ 的选择不影响 $R$ 的选择，但同一个 $R$ 可能对应多对 $(P,Q)$。为了计数，我们只需考虑 $R$ 的序列，所以只要 $R$ 能被某对已拥有点 $(P,Q)$ 所支持，该操作就可行。在 BFS 中，我们枚举所有三元组，只要恰好有两个点在当前集合中，就认为该 $R$ 可选（并且此时 $P,Q$ 就是那两个点，$R$ 是第三个点）。由于 $P,Q$ 是已拥有的，$R$ 未拥有，且圆包含所有点已经由预处理保证，所以该操作合法。而且，对于同一个 $R$，可能存在多对 $(P,Q)$ 都满足，但在我们的枚举中，每个 $R$ 可能会对应多个不同的三元组（指不同的 $P,Q$ 组合），但根据题目定义，这些不同的 $(P,Q)$ 被认为是同一个攻击计划（因为只关心 $R$ 序列），所以我们在 BFS 中应该避免重复计算同一个 $R$ 导致的相同新状态。然而，我们的枚举确实会把同一个 $R$ 但不同 $P,Q$ 的三元组视为不同的操作，从而导致重复计数。但题目说：“两个攻击计划仅在它们选择的 $R$ 序列不同时才视为不同”，如果 $R$ 相同但 $P,Q$ 不同，应该视为同一个计划。因此我们需要在 BFS 中，对于同一个 $R$，只考虑一次。但代码中未做去重，可能会多计。实际上，由于 $P,Q$ 的不同可能导致占领的三角形内部点集不同？注意，占领点集是由三角形决定的，而不同的 $P,Q$ 可能产生不同的三角形，虽然 $R$ 相同，但三角形 $\triangle PQR$ 可能不同，因此占领的点集也可能不同。所以不能简单对 $R$ 去重。必须区分不同的 $(P,Q)$ 组合，因为它们可能带来不同的内部点集。因此，题目中“两个计划使用相同的 $R$ 序列但不同的 $P,Q$ 视为相同”这句话的意思是：在同一个操作中，如果你选择了 $R$，具体使用哪一对 $P,Q$ 不影响计划，因为计划只关心 $R$。然而，如果不同的 $P,Q$ 导致占领了不同的点集，那么后续操作会不同，从而 $R$ 序列也可能不同（因为后续的 $R$ 依赖于当前拥有的点集）。所以，实际上计划由操作序列 $(R_1,R_2,\dots,R_k)$ 唯一确定，而每个 $R_i$ 是否可行取决于当时拥有的点集。但若在某个状态下，存在多对 $(P,Q)$ 使得同一个 $R$ 可行，它们应该被视为同一种选择（因为计划只记录 $R$）。因此我们在 BFS 中，对于一个固定的 $R$，应该只计一次，即使有多对 $(P,Q)$ 支持它。但代码中，对于每个三元组（每种 $(P,Q,R)$）都尝试了一次，可能会导致同一个 $R$ 被重复考虑，从而产生多个相同的后续状态（相同的 $nxt$）从同一种 $cur$ 出发，导致方案数多计。例如，如果 $R$ 有多个合法 $(P,Q)$ 对，且它们产生的 $nxt$ 相同，那么 ways[nxt] 会被累加多次，而实际上应该只加一次。因此代码存在计数错误。但题目给的示例通过了吗？不确定。实际正确的做法是：对于每个状态，枚举所有可能的 $R$，并检查是否存在一对已拥有的 $P,Q$ 使得 $(P,Q,R)$ 合法，如果存在，则使用该 $R$ 进行一次操作，并且占领的点集应该是所有可能的 $(P,Q,R)$ 对应三角形的内部点集的并集？还是任选一对？注意，操作一旦选定 $P,Q$，占领的点集就固定了，但同一个 $R$ 可能对应不同的 $P,Q$，导致占领的点集不同。但题目说两个计划只要 $R$ 序列相同就算相同，并没有说 $P,Q$ 的选择会影响占领哪些点。这就产生了歧义：如果 $R$ 相同但 $P,Q$ 不同，操作的结果（占领的点集）可能不同，那么 $R$ 序列就不能唯一确定结果，因此就不能只根据 $R$ 序列来定义计划。我们需要重新审视题意。

题中原话：“Two attack plans are considered different only if they differ in their choice of $R$ in some operation; in particular, two attack plans using the same choices of $R$ but different choices of $P$ and $Q$ are considered the same.” 这意味着，计划是由每次选择的 $R$ 构成的序列决定的，不关心 $P,Q$。但是，如果同一个 $R$ 有不同的可行 $(P,Q)$ 对，那么这些不同的 $(P,Q)$ 对应于同一个计划，但执行时具体占领的点集可能不同。然而，计划本身只是 $R$ 的序列，而执行时，我们可以任意选择支持它的 $P,Q$。所以，在计划执行过程中，对于给定的 $R$，我们总可以选择一对 $P,Q$ 使得操作可行。为了最大化后继的可能性，我们应该选择能使占领点集最大的 $P,Q$？还是说，计划是确定的，一旦 $R$ 序列固定，每个 $R$ 对应的 $P,Q$ 是任意的，但最终是否能占领所有塔，取决于能否找到一组 $P,Q$ 的选择序列使得过程可行。这类似于非确定性过程。题目要求统计 存在 一组 $P,Q$ 选择使得操作序列可行的方案数。所以，对于一个固定的 $R$ 序列，如果存在一种为每个 $R$ 挑选 $P,Q$ 的方式使得每一步的 $P,Q$ 都属于当时已拥有的点且圆包含所有点，那么该 $R$ 序列就是一个合法计划。因此，我们需要统计这样的 $R$ 序列的数量。

由于 $n \le 100$，我们可以用 BFS 在状态空间上搜索，但状态转移时，对于同一个 $R$，如果有多组 $(P,Q)$ 可行，我们应取这些 $(P,Q)$ 对应的占领点集的并集？因为我们可以选择最有利的那一对，使得占领尽可能多的点。实际上，为了达到目标，我们总是希望一次操作占领尽量多的点，所以我们可以认为，对于给定的当前状态 $S$ 和候选 $R$，我们可以选择任意可行的一对 $(P,Q)$，从而占领的点集是某个三角形内部的点，但我们可以选择其中最大的那个点集（即所有可行 $(P,Q)$ 对应点集的并集）。因为如果存在一种选择能占领更大的点集，那么它不会妨碍我们后续的操作（因为我们总是可以故意少占领一些，但多占领不会有害）。所以，为了计算最短操作次数，我们应该在每一步尽可能多占领点。因此，我们定义：从状态 $S$ 出发，对于每个不在 $S$ 中的点 $R$，如果存在 $P,Q \in S$ 使得 $(P,Q,R)$ 的圆包含所有点，那么我们可以选择将 $S$ 更新为 $S$ 与所有这样的 $(P,Q)$ 对应的三角形内点集的并集（因为我们可以选择最优的那一对）。这样，每个 $R$ 对应唯一的新状态（由所有可行 $(P,Q)$ 并集决定）。然后 BFS 统计最短路径，此时每个 $R$ 对应一条边，方案数就是不同 $R$ 序列的个数。这种理解更符合“计划由 $R$ 序列定义”的说法，因为一旦 $R$ 确定，我们可以自由选择 $P,Q$ 来最大化收益，所以 $R$ 序列唯一决定了结果状态的变化。

然而，上述代码并没有这样做，而是枚举了所有三元组，并对每个三元组独立进行了转移，这会导致对同一个 $R$ 的不同 $P,Q$ 产生不同的后继状态（尽管它们可能相同也可能不同），从而可能高估方案数。因此，代码可能并不是正确的实现，但作为题解，我们需要按照正确的理解来阐述算法。

修正的算法

由于题目限制 $n$ 很小（$n\le 100$，总和 $\le 1000$），我们可以用 BFS 状态压缩，但状态转移应按照上述“每个 $R$ 对应一种操作”来设计。具体步骤：

1. 预处理所有三元组 $(i,j,k)$，记录三个点以及圆是否包含所有点，同时计算三角形内点集 $mask_{i,j,k}$。
2. 对于每个状态 $S$（bitset），枚举所有不在 $S$ 中的点 $R$，检查是否存在 $P,Q\in S$ 使得 $(P,Q,R)$ 的圆包含所有点。如果存在，则计算所有这样的 $(P,Q)$ 对应的 $mask$ 的并集 $newMask$，然后新状态 $S' = S | newMask$。将 $(R, S')$ 视为一条边。
3. 从初始状态开始 BFS，记录距离和方案数。当有多个 $R$ 导致相同的 $S'$ 时，它们对应不同的 $R$ 序列（因为 $R$ 不同），所以方案数应累加；但如果同一个 $R$ 通过不同的 $(P,Q)$ 得到相同的 $S'$，只应算一次（因为 $R$ 相同）。但我们通过枚举 $R$ 已经避免了重复。

复杂度

状态数最多 $2^n$ 但实际很小，因为每次至少增加一个点，BFS 深度不超过 $n$。$n\le 100$，但 $n$ 的总和 $1000$，BFS 在随机数据上可能仍可接受，但最坏情况状态数可能很大。然而考虑到几何限制，实际可达状态数远小于 $2^n$，通常可以运行。

结论

本题是一道状态空间 BFS 题目，关键在于理解操作的条件和几何意义，并利用预处理所有可能的三元组和三角形内部点集，从而在状态间转移。由于 $n$ 较小，直接 BFS 可行。注意方案数计数时要按照题目对“攻击计划”的定义，仅由 $R$ 序列区分，因此每次枚举 $R$ 而非三元组。最终输出最短长度的方案数。若不可达，输出 $0$。