BOJ 18763 Knowledge oriented problem

Problem statement

정점 $n$개인 무방향 그래프 $G$가 주어진다. 정점이 $k$개인 path $P_k$와의 cartesian product $G \square P_{k}$의 cartesian product의 스패닝 트리의 개수를 구하여라. $n \le 500$, $k \le 10^{18}$.

Matrix-tree theorem

그래프 $G$의 Laplacian 을 $L_{G} := D_{G} - A_{G}$로 쓰자. $L_{G}$는 real symmetric matrix이고, positive semidefinite이므로 양의 실수 고윳값을 갖는다. Connected graph $G$에 대해 $L_{G}$는 rank $n-1$이 되는데, non-zero eigenvalue를 $\lambda_{1} \ge \cdots \ge \lambda_{n-1} > 0 = \lambda_{n}$이라고 두면, $G$의 스패닝 트리는 $$t(G) = \frac{1}{n}\lambda_{1} \cdots \lambda_{n-1}$$
개가 존재한다.

Laplacians of Cartesian products

두 그래프 $G, H$의 cartesian product $G \square H$의 Laplacian은 tensor product $$L_{G \square H} = L_{G} \otimes I + I \otimes L_{H}$$와 같이 나타난다. degree 행렬과 adjacency 행렬을 계산해보면 동일한 관계식을 알 수 있다. 두 행렬 $A, B$의 tensor product는 $$(A \otimes B) _ {ii', jj'} = A_{ij}B_{i'j'}$$
와 같이 정의된다.

$L_{G \square H}$의 eigenvector는 역시 각각의 eigenvector의 tensor product로 나타나는데, 고윳값이 $\lambda_{i}$인 $G$의 eigenvector $v_{i}$와 고윳값이 $\mu_{j}$인 $H$의 eigenvector $w_{j}$에 대해 $v_{i} \otimes w_{j}$가 고윳값 $\lambda_{i} + \mu_{j}$를 가진다는 걸 확인할 수 있다. 이제 우리가 계산할 건 $H = P_{k}$로 주어졌을 때
$$\frac{1}{nk}\prod_{(i, j) \neq (n, k)} (\lambda_{i} + \mu_{j})$$

를 계산하면 된다.

Laplacian polynomials

$lambda_{i}$를 정확하게 계산할 수도 없고, $O(nk)$개를 곱할 능력은 더 없다. 하지만 $L_{P_k}$의 characteristic polynomial $\phi_{k}(x) = (x - \mu_{1}) \cdots (x - \mu_{n-1})(x - \mu_{n})$를 계산할 수 있으면 $\phi_{k}(-\lambda_{i})$ 가 구하고자 하는 식에 나타나는 듯 보인다. 우선 $\phi_{k}(x)$에 주목하자.

$L_{P_k}$가 trilinear하다는 성질에서부터, 다음과 같은 점화식을 유도할 수 있다.
$$\phi_{0}(x)=0,\phi_{1}(x)=x,\quad\phi_{k}(x)=(x-2)\phi_{k-1}(x)-\phi_{k-2}(x)$$
이로부터 $\mu_{j}$의 값도 Chebyshev's polynomial과 엮어서 닫힌 형태로 쓸 수 있는데, 이 문제를 푸는 데 별 도움은 안 된다.

편의에 따라 $Q_{k}(x) = (-1)^{k}\phi_{k}(-x)/x$를 계산하기로 하자. 점화식은 다음과 같다.
$$Q_{0}(x)=0, Q_{1}(x)=1,\quad Q_{k}(x)=(x+2)Q_{k-1}(x) - Q_{k-2}(x)$$

일단 $Q_{k}(x) \bmod x^{n}$ 같은 걸 구하고 싶다면 $O(n \log n \log k)$ 정도에 구할 수 있는 식이 생긴 셈이다.

$O(n^3 \log k)$ 풀이 (TLE)

이제 우리가 원하는 식을 다시 $Q_{k}$를 이용하여 나타내면 다음과 같다.
$$\frac{1}{nk}\prod_{i=1}^{n-1} Q_{k}(\lambda_{i}) \cdot (\lambda_{1}\cdots\lambda_{n-1}) \cdot (\mu_{1}\cdots\mu_{k-1})$$
$G, H$의 nonzero eigenvalue를 묶은 $(n-1)(k-1)$개의 고윳값이 $Q_{k}$를 이용하여 묶였고, zero eigenvalue와 관련된 나머지 항들이 뒤따른다. 그런데 사실 위의 matrix tree theorem을 생각하면, 이 항들을 다시
$$\prod_{i=1}^{n-1} Q_{k}(\lambda_{i})t(G)t(P_{k})$$
로 정리할 수 있다. $t(G)$는 계산하기 어렵지 않고, $t(P_{k})=1$이니 결국 맨 처음 항이 문제다.

$L_{G}$는 real symmetric matrix니까 diagonalizable하다. $L_{G} = P\Lambda P^{T}$로 쓰자. $\Lambda = \mathrm{diag}(\lambda_{1}, \cdots, \lambda_{n})$으로 생각한다. 그러면 $Q_{k}(L_{G}) = PQ_{k}(\Lambda)P^{T}$가 되는 걸 확인할 수 있다. 이 때 $Q_{k}(\Lambda) = \mathrm{diag}(Q_{k}(\lambda_{1}), \cdots, Q_{k}(\lambda_{n}))$이다. 그러면 $Q_{k}(L_{G})$의 characteristic polynomial을 알면 $Q_{k}(\lambda_{1}) \cdots Q_{k}(\lambda_{n-1})$을 어렵지 않게 계산할 수 있다. $Q_{k}(0)=k$가 $10^{9}+7$의 배수인지 여부에 따른 subtle함이 있지만 크게 문제는 아니다.

$Q_{k}(L_{G}) = (L_{G} + 2I)Q_{k-1}(L_{G}) - Q_{k-2}(L_{G})$

를 이용해서 $O(n^{3} \log k)$에 계산하려고 하면, 당연히 TLE를 받는다.

Resultant

사실, 두 다항식의 스펙트럼에 관련된 잘 알려진 값이 존재한다. $f(x)=a(x-\lambda_{1})\cdots(x-\lambda_{d}), g(x)=b(x-\mu_{1})\cdots(x-\mu_{e})$에 대해, 그 둘의 resultant는 $$\mathrm{Res}(f, g) = a^{e}b^{d}\prod_{i,j} (\lambda_{i} - \mu_{j})$$로 정의한다.

사실 대수적으로 닫힌 체가 아니더라도 Resultant는 Sylvester Matrix의 determinant - 즉 계수들에 대한 식으로 표현할 수 있고, 근으로 쪼개지는 경우 위의 식과 정확히 일치한다. 다음은 우리가 활용할 Resultant의 몇 가지 성질들이다.

• $\mathrm{Res}(c, g) = c^{\deg g}$, $\mathrm{Res}(f, c) = c^{\deg f}$
• $\mathrm{Res}(f, g) = (-1)^{\deg f\deg g}\mathrm{Res}(g, f)$
• $g = fq + r$이라고 할 때, $\mathrm{Res}(f, g) = \mathrm{Res}(r, g) \cdot f_{0}^{\deg g - \deg r}$. 여기서 $f_{0}$는 $f$의 최고차항 계수이다.

그래서 결국 유클리드 호제법을 통해 $\mathrm{Res}(f, g)$를 subcubic time에 계산할 수 있다. $L_{G}$의 Characteristic polynomial $\psi(x)$에 대해, $\mathrm{Res}(\psi, Q_{k})$를 계산하자. $Q_{k}$는 너무 크니 $Q_{k}(x) \bmod \psi(x)$를 점화식을 통해 계산해주면 된다.

전체 시간복잡도는 $L_{G}$의 characteristic polynomial을 계산하는 $O(n^3)$이 된다.