题解：AT_abc323_g [ABC323G] Inversion of Tree

· · 题解

[ABC323G] Inversion of Tree

一道线性代数大杂烩。

前置知识：高斯消元，特征多项式，矩阵树定理，以及一些线性代数的理论知识。

对于这种无根树的数量计数问题，不难想到可以用矩阵树定理。但问题在于这里有逆序边的数量限制。

考虑类似 [省选联考 2020 A 卷] 作业题 的做法，把矩阵中的元素变成多项式从而计算答案。对于一条顺序边，其在矩阵上的边权为 1，逆序边边权为 x。设构造出的矩阵为 A，那么有 k 条逆序边的树的数量就是 [x^k] |A|。但这道题不像 作业题 一样要对 x^2 取模，所以复杂度是 \operatorname{O}(n^4) 的，无法通过。

考虑转换一下思想，设顺序边组成矩阵为 A，逆序边组成的矩阵为 B，那么 k 条逆序边的无根树的方案数就是 [x^k]|A+xB|（实际上这一句是废话），考虑有没有什么办法快速计算这个东西。

设 I 为单位矩阵，考虑一下两种特殊情况：

1. B=I

那么 |A+xB|=|A+xI|，不难发现这个式子就是特征多项式（|xI-A|），于是此时答案就是 -A 的特征多项式。

2. 存在 B' 满足 B'B=BB'=I（即 B 有逆元）

那么 |A+xB|=\frac{|AB'+xBB'|}{|B'|}=\frac{|xI-(-AB')|}{|B'|}，直接矩阵求逆一下就行了。

通过前面两个例子的启发，我们可以发现只要把 B 转化为 I 那么就是好做的。但问题在于 B 不一定有逆元。

我们不妨回忆矩阵求逆的过程，之所以 B 没有逆元是因为某一行没有主元。而在这道题中，我们除了 B 外还有一个矩阵 A，所以不妨通过 A 来让 B 拥有主元。

首先，在高斯消元时，如果 B 的第 i 行没有主元时可以直接把第 i 列 全部变成 0。不难发现，这时候我们将 A 的第 i 列乘上 x 就相当于交换 A，B 的第 i 列，这样就可以让 B 的第 i 行存在主元了。

当然，可能会出现操作后 B 的第 i 行也没有主元的情况，考虑这时候的状况。这说明 A，B 的第 i 列都为空，那么 |A+xB| 必然为 0, 所以此时特征多项式就是 0，可以特判掉。

通过这个操作，我们可以保证 B 能够变成 I，那么套一个特征多项式板子就好了。

时间复杂度 \operatorname{O}(n^3)。

code