RC-07 D

· · 题解

题目无非是给出 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 矩阵的特征值。且容易推广多张图。
因此，考虑用生成函数计量最终的乘积式中各种特征值的贡献，也即计算多项式

\prod_{i=1}^n (1 + (a_i-1)x^{a_i})

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

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