Domino Covering

https://www.acmicpc.net/problem/18607

 

 

 

 

 

 

 

문제의 답은 위와 같은데, 저대로 모든 값을 곱하는 것은 힘드니 Resultant를 통해 접근하자.

 

그래프 이론을 적용하면 경로 그래프의 완전 매칭의 수와 동치가 되므로 Binet–Cauchy formula에 의해 그래프의 교차하지 않는 경로들을 격자로 나타낸 행렬의 determinant를 이용해 식을 나타낼 수 있고 N, M에 각각 대응되는 식의 Resultant가 곧 타일링 가짓수가 된다.

 

${\LARGE f_{0} = 1 \text{ , } f_{1} = 1 +x \text{ , } f_{n} = (x + 2)f_{n - 1} - f_{n -2}}$

 

위와 같은 점화식을 행렬멱법을 통해 구해준 다음 Resultant를 취해주면된다.