COMPOUND ESCAPE 题解
题目大意
这是一个在 N×KN \times KN×K 网格中寻找最小生成树数量的问题。每个格子代表一个牛舍，相邻格子之间有门连接，每扇门都有解锁代价。我们需要找到使所有牛能聚集在一个格子的最小代价方案数。
解题思路
这是一个典型的最小生成树计数问题。我们需要：
1. 找到图的最小生成树的最小代价
2. 计算有多少种不同的最小生成树方案
算法分析
1. 图的构建
* 将 N×KN \times KN×K 网格看作图，每个格子是一个节点
* 水平相邻格子之间有水平边，垂直相邻格子之间有垂直边
* 每条边都有对应的权重（解锁代价）
2. 最小生成树计数
使用Kruskal算法的思想：
* 按权重从小到大排序所有边
* 对于相同权重的边，统计它们能连接的连通分量数
* 如果有 mmm 条边可以连接 kkk 个连通分量，那么这些边的选法数为 kkk（选择其中一条边）
3. 数学原理
设某权重 www 有 mmm 条边，这些边能连接 kkk 个连通分量，则这些边的选法数为 kkk。
复杂度分析
* 时间复杂度：O(NKlog(NK))O(NK \log(NK))O(NKlog(NK))
* 空间复杂度：O(NK)O(NK)O(NK)
题目代码
代码说明：1. 该算法通过构建网格图模型，将每个格子视为图中的节点，门的代价视为边的权重
2. 使用Kruskal算法思想，按边权重分组处理，计算最小生成树的数量
3. 对于相同权重的边，统计其连接连通分量的方式数，最终得到所有最小生成树方案数
4. 采用模运算防止整数溢出，确保结果正确性
