因为 \(det(A+xB)\) 和 \(det(A-\lambda I)\) 很像，所以可以考虑相互转化。
例：ABC323G。
【题意】
给定一个长度为 \(N\) 的排列 \(P=(P_1,P_2,\ldots,P_N)\)，其中 \(P\) 是 \(1\) 到 \(N\) 的一个排列。
请你求出编号为 \(1\) 到 \(N\) 的 \(N\) 个顶点的树中，满足以下条件的树的个数（对 \(998244353\) 取模），对于每个 \(K=0,1,\ldots,N-1\) 都要输出答案。
- 在树中，所有直接通过一条边相连的顶点对 \((u_i,v_i)\ (u_i < v_i)\) 中，满足 \(P_{u_i} > P_{v_i}\) 的对数恰好为 \(K\)。
\(2\leq N\leq 500\)，4s。
【题解】
看错题了 …… 还以为是给定树计数排列 ……
好像比较简单。看作一个有 \(n\) 个点的无向带权完全图，对于 \(i<j\)，若 \(p_i<p_j\) 则 \((i,j)\) 边权为 \(0\)，否则边权为 \(1\)。题目就是求边权和为 \(K\) 的生成树个数。
经典问题：图上标记一些边是重要的，一些边不重要。求恰好有 \(K\) 条重要边的生成树个数。
于是套用【算法理论/数学/矩阵树定理/CF917D】的暴力矩阵树做法，即可做到 \(O(n^4)\)。
但是四次方不太能过，考虑优化。
注意到暴力矩阵树做法里，求的东西形如 \(det(A+xB)\)，其中 \(A\) 是不重要边对应的矩阵，\(B\) 是重要边对应的矩阵。
接下来是一个比较 tricky 的东西（？）。对于所有 \(det(A+xB)\) 的东西都能做 \(O(n^3)\)。
我们发现，这个东西长得很像特征多项式 \(det(A-\lambda I)\)，而特征多项式是可以 \(O(n^3)\) 求的，所以考虑往上凑一凑。
-
当 \(B=I\) 时，\(det(A+xB)=det(A+xI)=det(-A-xI)\)，所以此时答案就是 \(-A\) 的特征多项式。
-
当 \(B\) 满秩。满秩则可以通过初等变换变成单位矩阵。注意这里对 \(B\) 变换时 \(A\) 也要一起变，因为是对 \(A+xB\) 这个整体求行列式。变换完之后变成 \(det(A'+xI)\)，就是求 \(-A\) 的特征多项式。
另一种理解方式是满秩等价于可逆。设 \(D=B^{-1}\)，这样 \(det(A+xB)=\frac{det((A+xB)D)}{det(D)}=\frac{det(AD+xI)}{det(D)}\)。
-
\(B\) 可能不存在逆的情况。
有了上面两种情况的启发，我们会希望把 \(B\) 转化为 \(I\) 的形式。
仍然做变换试图消成单位矩阵。若某次消元失败了，说明 \(B\) 的某一行全是 \(0\)。
但是因为最终是求 \(A+xB\) 这个整体，所以我们可以让 \(A\) 的这一行来拯救 \(B\) 的这一行：让 \(A\) 的这一行复制过来。这样相当于对 \(A+xB\) 的一行乘以 \(x\)，最终把这个 \(x\) 除回来即可。
参考这个例子（这个例子是从左到右消元的）：
注意：把这一行复制过来之后要让前面的行消元这行。
有可能复制过来之后依然无法让第 \(i\) 行第 \(i\) 列非零，但是因为复制过来时让前面的行消元这行，\(A\) 也是要同步做的。所以可能消元之后虽然 \(B_{i,i}=0\)，但是 \(A\) 的这一行又变成非零了，继续复制过来消元，直到 \(B_{i,i}\neq 0\) 了停止，或者复制的次数超过 \(n\)。
因为原本的特征多项式肯定不超过 \(n\) 次。如果复制的次数超过 \(n\) 了，说明特征多项式是 \(x^{n+1}\) 的倍数，所以特征多项式肯定是全 \(0\)。
如果没有返回 \(0\)，那就是消元成功了，求 \(A'\) 的特征多项式即可。