BOJ 18763 Knowledge oriented problem

2025. 4. 17. 09:01알고리즘 문풀/BOJ 연습

Problem statement

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

Matrix-tree theorem

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

Laplacians of Cartesian products

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

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

를 계산하면 된다.

Laplacian polynomials

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

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

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

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

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

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

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

Qk(LG)=(LG+2I)Qk1(LG)Qk2(LG)Q_{k}(L_{G}) = (L_{G} + 2I)Q_{k-1}(L_{G}) - Q_{k-2}(L_{G})

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

Resultant

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

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

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

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

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

'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글

BOJ 21268 Do Use FFT  (0) 2025.01.31
BOI 2016 Swap  (0) 2025.01.22
2021 Jan-Feb Problem Solving  (0) 2021.03.04
BOJ 10129 작은 새  (0) 2020.02.10
BOJ 17962 Game on a Tree + BOJ 3419 Racing Car Trail  (0) 2020.01.28