[백준 21117] Number of Colorful Matchings [Ruby III]

 

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

21117번: Number of Colorful Matchings

 

 알아두어야 할 배경지식이 몇 개 있다. 자세한 사항은 https://en.wikipedia.org/wiki/Permanent_(mathematics) 여기를 참고했다.

 

 1. 이분 그래프 G의 adjoint matrix는 $\left[\begin{array}{cc}O& A\\ A^T& O\end{array}\right]$ 꼴이다. 여기서 A만을 남길 수 있다. 이분 그래프의 두 partition의 size가 같으면 A는 정사각행렬이다. 즉 이 문제의 조건에서 A는 정사각행렬이다.

 2. 이분 그래프에서 perfect matching의 수는 $\mathrm{per}(A)$이다. 여기서 per은 permanent라 불리는 값이다. permanent의 계산 방법은 determinant와 동일하지만, 부호는 모두 +를 사용한다. 다시 말해,

 

$$\mathrm{per}(A)=\sum _{\sigma }\prod a_{i,\sigma (i)}$$

 

 이것의 증명은 자명하다. 그냥 주어진 식의 시그마를 잘 풀어헤치기만 하면 된다. 선택한 permutation이 G의 edge로만 구성되어 있다면 항의 값은 1이 되고, 아니면 0이 된다. 

 3. permanent의 계산을 다항 시간 안에 하는 것은 매우 어렵다. 만약 permanent의 계산을 다항 시간에 하는 방법이 발견된다면 P = NP가 증명되며 필즈상, 튜링상 다이렉트 열차를 탈 수 있다.

 4. 하지만 만약 2로 나눈 값만을 구하고 싶다면, 체 F2 위에서 +1 = -1이므로, permanent는 determinant와 동일하다.

 

 문제에서는 그냥 perfect matching 개수만 구하면 되는 게 아니고, 빨간색이 k개이고 파란색이 n-k개인 perfect matching 수를 구해야 한다. 머리를 좀 굴려 보면, 비슷한 문제로 "정확히 k개의 비트만 켜진 n비트 문자열의 개수는?" 같은 문제를 생각해볼 수 있다. 이 문제의 정답은 $(x+1{)}^n$의 전개식에서 $x^k$의 계수이다. 비슷하게, 풀고자 하는 문제의 정답은 $\mathrm{per}(Ax+B)$를 구한 뒤 전개하여 각 행의 계수를 구하면 알 수가 있다. 나는 증명을 엄밀하게는 하지 않았는데, 앞서 permanent 값과 perfect matching 수가 어떻게 관련 있는지를 잘 떠올려보면 증명 가능할 듯하다. 결국 x^k term은 모든 permutation 중 E(G)에 속하는 것들 중 빨간색이 k개이고, 파란색이 n-k개인 간선의 수를 모두 합침으로써 구할 수가 있다.

 

 결국 $det(Ax+B)$를 계산하면 문제는 풀린다. 이걸 구하는 것도 사실 다른 과정만큼이나 어려운 건 마찬가지. 만약 A가 invertible이라면 문제는 $B{A}^{-1}$의 characteristic polynomial을 구하는 문제로 쉽게 치환할 수 있다. characteristic polynomial은 많아야 O(n^4)에 계산할 수 있다. A가 invertible이 아닐 경우, det=0이므로 A를 삼각화하면 마지막 행이 자연스럽게 0이 된다. 그렇다면 결국 $Ax+B$의 마지막 행은 x와 invariant한 상수 행이 되고, 이 행들끼리 column operation을 잘 돌려주면 단 하나의 1만 남기고 나머지 성분을 다 0으로 만들어줄 수 있다. 이제 $det\left[\begin{array}{cc}1& O\\ O& A\end{array}\right]=detA$를 쓰면 행 하나가 날아간다. 이 과정을 반복해주면 언젠가는 A가 invertible이 된다. 만약 그렇지 않다면 A는 소멸해버릴 텐데 그럴 리가 없기 때문.

 

 마지막으로, characteristic polynomial을 구하는 알고리즘은 보통 O(n^3)에 구현 가능하지만 이 경우는 체가 F2라서 알고리즘이 먹히지 않는다. 대신 O(n^4 / 64)에 구현 가능한 Samuelson 알고리즘이라는 것이 있다. 알고리즘 자체는 O(n^4)인데, bitset을 쓰면 행렬 연산을 64배 빠르게 할 수 있다는 점을 이용하면 된다. 전체 시간복잡도는 O(n^4 / 64)이다.