Official

G - Inversion of Tree Editorial by en_translator

This problem features Kirchhoff’s theorem and an algorithm of finding the determinant of a matrix whose elements are linear functions.

Kirchhoff’s theorem

Kirchhoff’s matrix tree theorem has already been appeared several times in ABC (AtCoder Beginner Contest), so please refer to the related articles.

The theorem can also be applied to this problem too. The key is that the theorem allows us to assign a positive-integer-value weight to each edge. Assigning weight \(c\) on edge \((u,v)\) means there are \(c\) edges.

In this problem, let the weight of edge with \(P_u>P_v\) be \(x\), and that with \(P_u<P_v\) be \(1\). Applying Kirchhoff’s theorem, we see that the coefficient on \(x^i\) coincides with the answer for \(K=i\) in the original problem.

After all, this problem boils down to finding the determinant of a matrix whose element is a linear function. Now, let \(M_0 + M_1 x\) be the matrix whose determinant we seek.

\(\mathrm{O}(N^4)\) solution

In most cases, \(\mathrm{O}(N^4)\) solution is sufficient, so we first explain it. Since the sought determinant is of degree at most \(N\), we can assign \(0,1,\ldots,N\) to \(x\) and reconstruct the coefficients from them. Evaluating a determinant costs \(\mathrm{O}(N^3)\) time, so this solution works in a total of \(\mathrm{O}(N^4)\) time.

\(\mathrm{O}(N^3)\) solution

We introduce an \(\mathrm{O}(N^3)\) solution that exploits a fast algorithm of finding characteristic polynomial of a matrix.

The characteristic polynomial of an \(N\times N\) matrix \(M\) is defined as \(\det({xI - M})\), where \(I\) is the \(N\times N\) identity matrix.

It is known that the characteristic polynomial can be obtained in an \(\mathrm{O}(N^3)\) time. (Reference: Library checker Characteristic Polynomial) Thus, it is sufficient to transform the sought determinant into the form of characteristic polynomial.

If \(M_1\), the coefficient on \(x\) in \(\det({M_0 + M_1 x })\), is regular, then that coefficient can be replaced with \(I\), considering elementary row and column operations.

Specifically, if we take matrices \(A\) and \(B\) such that \(I=A M_1 B\), then it can be deformed into

\[\det({M_0 + M_1 x })= \frac{1}{\det A \det B}\det(A (M_0 + M_1 x)B) = \frac{1}{\det A \det B}\det(AM_0B + I x), \]

so it is sufficient to find the characteristic polynomial of the matrix \(AM_0B\).

If \(M_1\) is not regular, we take an arbitrary random value \(a\) to let \(y=x+a\), and try to find \(\det{(M_0 +y M_1)} = \det{((M_0+aM_1) +x M_1)}\).

Here, by letting \(z=y^{-1}\), it is enough to find the determinant of \(\det{( z (M_0+aM_1) + M_1)}\). As we are taking \(a\) at random, we expect that \(M_0 + aM_1\) is regular with high probability.

Since we can apply the method described above against a regular matrix, we successfully evaluate \(\det{(M_0 +y M_1)} \). Finally, we replace \(x\) with \((x-a)\) to obtain the sought determinant.

Reference

posted:
last update: