自动搬运

查看原文

来自洛谷，原作者为

	LucidDawn **

搬运于2025-08-24 22:44:30，当前版本为作者最后更新于2023-02-03 18:29:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目无非是给出 $G = K_{a_1} \mathop\square K_{a_2} \mathop\square \cdots \mathop\square K_{a_n}$，求其生成树个数。其中 $\square$ 为图的 Cartesian 积。
根据 Matrix-Tree 定理，我们知道答案即为其 Laplacian 矩阵的所有非零特征值之积的 $(\prod a_i)^{-1}$ 倍。
而 $K_m$ 的 Laplacian 矩阵的特征多项式即 $\lambda(\lambda-m)^{m-1}$。

而根据 [1]，两张图的 Cartesian 积的 Laplacian 矩阵的特征值为 $\lambda_i + \mu_j$，其中 $\lambda_i, \mu_j$ 分别为各自的 Laplacian 矩阵的特征值。且容易推广多张图。
因此，考虑用生成函数计量最终的乘积式中各种特征值的贡献，也即计算多项式

的系数取模 $99824435\mathbf 2$ 的结果。本题中仅需 $O(n \sum a_i)$ 即可。

[1] 潘佳奇，浅谈线性代数与图论的关系，IOI 2021 中国国家集训队论文