CountingSpanningTrees - 题解

标签与难度

标签: 图论, 生成树计数, 矩阵树定理, 组合数学, 二分图, 差分数组难度: 2200

题目大意喵~

主人，你好呀！这道题是关于一个很特殊的二分图的呢，让我来给你分析一下吧~

题目给了我们一个二分图，它有两组顶点，我们叫它们 $X$ 部和 $Y$ 部。

$X$ 部有 $n$ 个顶点，分别是 $x_1, x_2, \dots, x_n$ 。
$Y$ 部有 $m$ 个顶点，分别是 $y_1, y_2, \dots, y_m$ 。

这个图的连接方式非常特别哦：对于每一个 $X$ 部的顶点 $x_i$ ，它会和 $Y$ 部的前 $a_i$ 个顶点相连，也就是连接 $y_1, y_2, \dots, y_{a_i}$ 。

我们的任务就是，对于这样一个图，计算它有多少棵不同的生成树。结果需要对一个给定的模数 mod 取模，喵~

举个栗子：如果 $n=2, m=3$ , $a_1=2, a_2=3$ 。那么 $x_1$ 连接 $y_1, y_2$ 。 $x_2$ 连接 $y_1, y_2, y_3$ 。我们就要计算这个图的生成树数量啦！

解题思路分析

一看到“生成树计数”，我的DNA就动了，首先想到的肯定是矩阵树定理 (Matrix Tree Theorem) 啦！这个定理可是解决生成树计数问题的万能钥匙哦。它告诉我们，一个图的生成树数量等于其拉普拉斯矩阵 (Laplacian Matrix) 的任意一个代数余子式的值。

但是，这个图的顶点总数是 $n+m$ ，可能会很大（ $n, m \le 10^5$ ），所以拉普拉斯矩阵的大小会是 $(n+m) \times (n+m)$ 。直接计算行列式的话，时间复杂度大概是 $O((n+m)^3)$ ，这实在是太慢了，肯定会超时的说！我的爪爪都算麻了也算不完呐。

所以，直接用通用的矩阵树定理是行不通的。我们需要寻找这个图的特殊性质！

这个图最特别的地方就在于它的“邻域嵌套”性质。我们来看看 $X$ 部顶点的邻居们：

$N(x_i)$ 表示 $x_i$ 的邻居集合，也就是 $\{y_1, y_2, \dots, y_{a_i}\}$ 。如果我们把 $X$ 部的顶点按照它们对应的 $a_i$ 值从小到大排序，假设排序后是 $x_{p_1}, x_{p_2}, \dots, x_{p_n}$ ，满足 $a_{p_1} \le a_{p_2} \le \dots \le a_{p_n}$ 。那么它们的邻居集合就满足 $N(x_{p_1}) \subseteq N(x_{p_2}) \subseteq \dots \subseteq N(x_{p_n})$ 。

对于这种具有邻域嵌套性质的特殊二分图（也叫阈下二分图 (Threshold Bipartite Graph)），有一个非常漂亮的定理，可以直接计算生成树的数量，完全不需要去算那个复杂的行列式啦！

神奇的定理：对于一个具有邻域嵌套性质的二分图，其生成树数量为：

T(G) = \left( \prod_{i=1}^{n-1} d'_i \right) \cdot \left( \prod_{j=1}^{m-1} e'_j \right)

其中， $d'_1, \dots, d'_n$ 是 $X$ 部所有顶点的度数，从小到大排序后的序列。 $e'_1, \dots, e'_m$ 是 $Y$ 部所有顶点的度数，从小到大排序后的序列。

也就是说，我们只需要：

计算出 $X$ 部所有顶点的度数。
计算出 $Y$ 部所有顶点的度数。
将这两组度数分别排序。
将 $X$ 部最小的 $n-1$ 个度数相乘，再将 $Y$ 部最小的 $m-1$ 个度数相乘，最后把这两个积再乘起来，就是答案啦！是不是很简单喵？

那么，下一步就是计算度数了。

1. 计算 $X$ 部顶点的度数 $x_i$ 连接了 $a_i$ 个 $Y$ 部的顶点，所以它的度数 $d(x_i)$ 就等于 $a_i$ 。这个题目直接就告诉我们了呢！

2. 计算 $Y$ 部顶点的度数 $y_j$ 的度数 $d(y_j)$ 是多少呢？它等于所有连接到它的 $X$ 部顶点的数量。一个顶点 $x_i$ 会连接到 $y_j$ 当且仅当 $a_i \ge j$ 。所以：

d(y_j) = |\{i \mid a_i \ge j\}|

直接计算这个会比较慢，是 $O(N \cdot M)$ 的。但我们可以用一个更聪明的办法——差分数组！我们可以创建一个辅助数组 counts，大小为 $m+2$ 。对于每个 $a_i$ ，它都对 $y_1, \dots, y_{a_i}$ 的度数贡献了 1。这相当于一个区间增加操作。我们可以这样操作：

对于每个 $a_i$ ，我们让 counts[1] 增加 1，counts[a_i + 1] 减少 1。
遍历完所有的 $a_i$ 后，我们对 counts 数组求前缀和。degree_y[j] = degree_y[j-1] + counts[j]。这样，degree_y[j] 就神奇地变成了 $y_j$ 的真实度数了！这个过程只需要 $O(n+m)$ 的时间，非常高效！

算法步骤总结:

读取输入 $n, m, \text{mod}$ 和数组 $a_1, \dots, a_n$ 。
$X$ 部的度数数组就是 $a$ 数组本身。
使用差分数组和前缀和的方法，在 $O(n+m)$ 时间内计算出 $Y$ 部所有顶点 $y_1, \dots, y_m$ 的度数，存入 y_degrees 数组。
对 $a$ 数组和 y_degrees 数组分别进行升序排序。
初始化答案 ans = 1。
将 $a$ 数组的前 $n-1$ 个元素（也就是最小的 $n-1$ 个度数）依次乘到 ans 中，每次乘法后取模。
将 y_degrees 数组的前 $m-1$ 个元素（也就是最小的 $m-1$ 个度数）依次乘到 ans 中，每次乘法后取模。
输出最终的 ans。

关于连通性的小插曲: 如果图不连通，生成树的数量就是 0。我们的图什么时候会不连通呢？因为所有 $x_i$ 都至少连接 $y_1$ （题目保证 $a_i \ge 1$ ），所以 $X$ 部和 $Y$ 部之间总是连通的。唯一可能不连通的情况是某个 $y_j$ 变成了孤立点。最容易被孤立的是 $y_m$ ，它需要有 $a_i \ge m$ 才能被连接。如果所有 $a_i$ 都小于 $m$ ，那么 $y_m$ 的度数就是 0，图就不连通。不过，我们的算法已经完美地处理了这种情况！如果 $d(y_m) = 0$ ，那么 y_degrees 数组里就会有一个 0。排序后，这个 0 会被放在最前面。只要 $m>1$ ，在计算乘积时就会乘上这个 0，最终答案自然就是 0 啦，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦！每一行都有详细的注释，希望能帮助你理解，呐~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 使用 long long 来防止乘法过程中的溢出
using ll = long long;

void solve() {
    int n, m;
    ll mod;
    // 循环读取输入，直到文件末尾
    while (std::cin >> n >> m >> mod) {
        // x_degrees 存储 X 部顶点的度数，就是输入的 a 数组
        std::vector<ll> x_degrees(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> x_degrees[i];
        }

        // --- 计算 Y 部顶点的度数 ---
        // 使用差分数组技巧来高效计算
        // diff[j] 存储度数在 j 点的变化量
        std::vector<ll> diff(m + 2, 0); 
        for (int i = 0; i < n; ++i) {
            // 每个 x_i 对 y_1 到 y_{a_i} 的度数都有贡献
            // 相当于在区间 [1, a_i] 上 +1
            diff[1]++;
            if (x_degrees[i] + 1 <= m) {
                diff[x_degrees[i] + 1]--;
            }
        }
        
        // y_degrees 存储 Y 部顶点的度数
        std::vector<ll> y_degrees(m);
        ll current_degree = 0;
        for (int j = 0; j < m; ++j) {
            // 通过前缀和计算出每个 y_j 的真实度数
            current_degree += diff[j + 1];
            y_degrees[j] = current_degree;
        }

        // --- 排序度数 ---
        std::sort(x_degrees.begin(), x_degrees.end());
        std::sort(y_degrees.begin(), y_degrees.end());

        // --- 计算最终答案 ---
        // 根据定理，将 X 部最小的 n-1 个度数和 Y 部最小的 m-1 个度数相乘
        ll ans = 1;
        
        // 乘上 X 部的度数
        for (int i = 0; i < n - 1; ++i) {
            ans = (ans * x_degrees[i]) % mod;
        }

        // 乘上 Y 部的度数
        for (int i = 0; i < m - 1; ++i) {
            ans = (ans * y_degrees[i]) % mod;
        }
        
        std::cout << ans << std::endl;
    }
}

int main() {
    // 加速 C++ IO
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

时间复杂度: $O(N \log N + M \log M)$
- 读取输入和初始化差分数组： $O(N)$ 。
- 通过差分数组计算 $Y$ 部的度数： $O(M+N)$ 。
- 对 $X$ 部的度数数组排序： $O(N \log N)$ 。
- 对 $Y$ 部的度数数组排序： $O(M \log M)$ 。
- 计算最终的乘积： $O(N+M)$ 。
- 所以总的时间复杂度由排序决定，为 $O(N \log N + M \log M)$ 。
空间复杂度: $O(N+M)$
- 我们需要 $O(N)$ 的空间来存储 $X$ 部的度数。
- 我们需要 $O(M)$ 的空间来存储 $Y$ 部的度数以及计算它时用的差分数组。
- 总的空间复杂度就是 $O(N+M)$ 的说。

知识点总结

这道题虽然看起来是图论，但核心其实是发现图的特殊结构，并应用一个不那么常见的定理，喵~

生成树计数: 基础工具是矩阵树定理，但对于大规模或有特殊结构的图，通常有更简单的公式。
特殊图的性质: 学会观察图的性质！本题中的“邻域嵌套”就是一个关键突破口。识别出它是阈下二分图，问题就解决了一大半。
阈下二分图的生成树计数公式: $\prod_{i=1}^{n-1} d'_i \cdot \prod_{j=1}^{m-1} e'_j$ 。记住这个公式，下次遇到类似问题就能秒杀啦！
差分数组: 一个非常实用的小技巧，能将多次区间修改操作优化为一次前缀和计算。在处理类似“对 $1 \dots k$ 的所有元素进行操作”的问题时特别有效。

希望我的题解对你有帮助哦！要继续努力，在算法的世界里探索更多有趣的东西，加油喵！(ฅ'ω'ฅ)

CountingSpanningTrees - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​