# 超时空军团：题解

## 解法比较

出题人的网格建图方案在整个网格上建立二维线段树，支持正方形中的人数及最大年龄查询。对每个要求，用人数随半径不减的性质二分最小切比雪夫半径，再取该闭正方形内年龄最大的点连边。矩阵树定理、拉普拉斯行列式及删除顺序的阶乘因子都已在出题人解法中，证明见下文。二分必须包括半径零，并继续寻找最小可行半径；才能找到满足要求的最小正方形。

令网格为 $N\times M$ 、有效点数为 $K$ 、要求总数为 $S$ .网格方案存储为 $O(NM+K^2+S)$ ，建图查询上界为 $O(S\log(\max(N,M)+1)\log(N+1)\log(M+1))$ ，另有网格建立及插点开销。Codex（GPT-6）采用的实现逐中心排序全部有效点的距离，按等距离整组处理，建图为 $O(K^2\log(K+1)+S)$ ，空间为 $O(K^2+S)$ ；两者后续行列式计算相同。Codex 实现适合点数较少而网格较大的条件，代价是显式枚举点对，不能泛化为任意稠密场景下都更快。

## 构造通信图

建筑数仅有 $K\le200$ ，无需为整个网格建立二维数据结构。

对每座建筑 $i$ ，计算它到所有建筑的切比雪夫距离（两个坐标差绝对值的最大值），包含自身距离 $0$ ，并按距离排序。阈值 $D$ 对应的最小半径就是排序中第 $D$ 项的距离。

将距离相同的项一起处理，先更新这一整组内的最大建造时间，再把当前最新建筑记录到组内的每个位置。这样查询第 $D$ 项时，会包含半径边界上的全部建筑。坐标重叠时，距离为 $0$ 的整组同样参与处理。

若查询得到的建筑不是自身，就加入一条无向边；用布尔邻接矩阵去重。总建图时间为 $O(K^2\log K+\sum_i P_i)$ .

## 最优删除方案对应生成树

设通信图共有 $E$ 条边。连通图至少保留 $K-1$ 条边；保留任意一棵生成树就可以删除其余所有边。因此最多删除

$$q=E-K+1$$

条边。

每个最优删除方案最后恰好剩下一棵生成树。反过来，固定一棵生成树后，其他 $q$ 条边可以按任意顺序删除，因为该生成树始终完整保留，连通性不会丢失。不同的剩余树对应不同的删除边集合，因此不会重复计数。

若生成树数量为 $\tau$ ，答案就是

$$\tau\cdot q!\pmod{\mathrm{mod}}$$

## 矩阵树定理

构造拉普拉斯矩阵 $L$ ：对角元为度数；不同顶点之间有边时为 $-1$ ，否则为 $0$ .删去同一个顶点对应的行和列，得到 $(K-1)$ 阶矩阵 $A$ .矩阵树定理给出 $\tau=\det A$ .

$K=1$ 时余子式为空矩阵，其行列式约定为 $1$ ，也恰好表示唯一的空生成树。

## 合数模数下的行列式

不能假定非零主元存在模逆元。这里采用欧几里得消元，始终把元素保存为 $[0,\mathrm{mod}-1]$ 内的代表元。

处理第 $i$ 列时，对每个后续行 $j$ ，只要 $A_{ji}\ne0$ ，就执行：

1. 取普通整数商 $h=\lfloor A_{ii}/A_{ji}\rfloor$ .
2. 第 $i$ 行减去第 $j$ 行的 $h$ 倍，所有元素对 $\mathrm{mod}$ 取模。
3. 交换第 $i,j$ 行，并将行列式符号取反。

行倍加不改变行列式，交换两行改变符号。这些恒等式在任意整数模数下都成立。当前列的两个代表元按欧几里得算法递减，故循环一定终止。若消元后的主元为零，行列式为零；否则继续处理，最终乘所有对角元及交换符号。

必须记录每一次换行的负号，不能使用仅适用于素数模数的费马逆元消元。最终再乘 $q!$ 即可。

## 正确性

距离排序与完整处理同距组得到每个阈值的最小半径及范围内最新建筑，所以构图符合题意。最 优删除序列与“生成树加其余边的排列”一一对应。矩阵树定理给出生成树数量，欧几里得行变换在任意模数下保持正确的行列式值及符号，因此输出等于所求序列数。

## 复杂度

建图为 $O(K^2\log K+\sum_iP_i)$ ，行列式的保守上界为 $O(K^3\log\mathrm{mod})$ ，阶乘为 $O(E)$ .额外空间为 $O(K^2+\sum_iP_i)$ ，在本题约束下为 $O(K^2)$ .

建造时间与模乘使用 64 位整数。坐标只用于建筑之间的距离，不分配与 $NM$ 成正比的存储。