Problem statement
정점 n개인 무방향 그래프 G가 주어진다. 정점이 k개인 path Pk와의 cartesian product G□Pk의 cartesian product의 스패닝 트리의 개수를 구하여라. n≤500, k≤1018.
Matrix-tree theorem
그래프 G의 Laplacian 을 LG:=DG−AG로 쓰자. LG는 real symmetric matrix이고, positive semidefinite이므로 양의 실수 고윳값을 갖는다. Connected graph G에 대해 LG는 rank n−1이 되는데, non-zero eigenvalue를 λ1≥⋯≥λn−1>0=λn이라고 두면, G의 스패닝 트리는 t(G)=n1λ1⋯λn−1
개가 존재한다.
Laplacians of Cartesian products
두 그래프 G,H의 cartesian product G□H의 Laplacian은 tensor product LG□H=LG⊗I+I⊗LH와 같이 나타난다. degree 행렬과 adjacency 행렬을 계산해보면 동일한 관계식을 알 수 있다. 두 행렬 A,B의 tensor product는 (A⊗B)ii′,jj′=AijBi′j′
와 같이 정의된다.
LG□H의 eigenvector는 역시 각각의 eigenvector의 tensor product로 나타나는데, 고윳값이 λi인 G의 eigenvector vi와 고윳값이 μj인 H의 eigenvector wj에 대해 vi⊗wj가 고윳값 λi+μj를 가진다는 걸 확인할 수 있다. 이제 우리가 계산할 건 H=Pk로 주어졌을 때
nk1(i,j)=(n,k)∏(λi+μj)
를 계산하면 된다.
Laplacian polynomials
lambdai를 정확하게 계산할 수도 없고, O(nk)개를 곱할 능력은 더 없다. 하지만 LPk의 characteristic polynomial ϕk(x)=(x−μ1)⋯(x−μn−1)(x−μn)를 계산할 수 있으면 ϕk(−λi) 가 구하고자 하는 식에 나타나는 듯 보인다. 우선 ϕk(x)에 주목하자.
LPk가 trilinear하다는 성질에서부터, 다음과 같은 점화식을 유도할 수 있다.
ϕ0(x)=0,ϕ1(x)=x,ϕk(x)=(x−2)ϕk−1(x)−ϕk−2(x)
이로부터 μj의 값도 Chebyshev's polynomial과 엮어서 닫힌 형태로 쓸 수 있는데, 이 문제를 푸는 데 별 도움은 안 된다.
편의에 따라 Qk(x)=(−1)kϕk(−x)/x를 계산하기로 하자. 점화식은 다음과 같다.
Q0(x)=0,Q1(x)=1,Qk(x)=(x+2)Qk−1(x)−Qk−2(x)
일단 Qk(x)modxn 같은 걸 구하고 싶다면 O(nlognlogk) 정도에 구할 수 있는 식이 생긴 셈이다.
O(n3logk) 풀이 (TLE)
이제 우리가 원하는 식을 다시 Qk를 이용하여 나타내면 다음과 같다.
nk1i=1∏n−1Qk(λi)⋅(λ1⋯λn−1)⋅(μ1⋯μk−1)
G,H의 nonzero eigenvalue를 묶은 (n−1)(k−1)개의 고윳값이 Qk를 이용하여 묶였고, zero eigenvalue와 관련된 나머지 항들이 뒤따른다. 그런데 사실 위의 matrix tree theorem을 생각하면, 이 항들을 다시
i=1∏n−1Qk(λi)t(G)t(Pk)
로 정리할 수 있다. t(G)는 계산하기 어렵지 않고, t(Pk)=1이니 결국 맨 처음 항이 문제다.
LG는 real symmetric matrix니까 diagonalizable하다. LG=PΛPT로 쓰자. Λ=diag(λ1,⋯,λn)으로 생각한다. 그러면 Qk(LG)=PQk(Λ)PT가 되는 걸 확인할 수 있다. 이 때 Qk(Λ)=diag(Qk(λ1),⋯,Qk(λn))이다. 그러면 Qk(LG)의 characteristic polynomial을 알면 Qk(λ1)⋯Qk(λn−1)을 어렵지 않게 계산할 수 있다. Qk(0)=k가 109+7의 배수인지 여부에 따른 subtle함이 있지만 크게 문제는 아니다.
Qk(LG)=(LG+2I)Qk−1(LG)−Qk−2(LG)
를 이용해서 O(n3logk)에 계산하려고 하면, 당연히 TLE를 받는다.
Resultant
사실, 두 다항식의 스펙트럼에 관련된 잘 알려진 값이 존재한다. f(x)=a(x−λ1)⋯(x−λd),g(x)=b(x−μ1)⋯(x−μe)에 대해, 그 둘의 resultant는 Res(f,g)=aebdi,j∏(λi−μj)로 정의한다.
사실 대수적으로 닫힌 체가 아니더라도 Resultant는 Sylvester Matrix의 determinant - 즉 계수들에 대한 식으로 표현할 수 있고, 근으로 쪼개지는 경우 위의 식과 정확히 일치한다. 다음은 우리가 활용할 Resultant의 몇 가지 성질들이다.
- Res(c,g)=cdegg, Res(f,c)=cdegf
- Res(f,g)=(−1)degfdeggRes(g,f)
- g=fq+r이라고 할 때, Res(f,g)=Res(r,g)⋅f0degg−degr. 여기서 f0는 f의 최고차항 계수이다.
그래서 결국 유클리드 호제법을 통해 Res(f,g)를 subcubic time에 계산할 수 있다. LG의 Characteristic polynomial ψ(x)에 대해, Res(ψ,Qk)를 계산하자. Qk는 너무 크니 Qk(x)modψ(x)를 점화식을 통해 계산해주면 된다.
전체 시간복잡도는 LG의 characteristic polynomial을 계산하는 O(n3)이 된다.