문제 링크
- http://icpc.me/21265
사용 알고리즘
- LGV 정리
- 가우스 소거법
시간복잡도
- $O(K^4)$
풀이
값이 $x$인 격자와 $x+1$인 격자 사이를 가로지르는 경계선은 위/오른쪽으로 이동하는 경로 형태입니다. 따라서 이 문제는 경로를 $(R, C)$ 왼쪽 위에 $V-1$개, 오른쪽 아래에 $K-V$개 만드는 경우의 수를 세는 문제라고 생각할 수 있습니다. 이때 경로는 겹칠 수 있지만 교차하지는 않습니다.
잠시 $A(R, C) = V$ 조건을 무시해 봅시다. 이 조건이 없으면 단순히 경로를 $K-1$개 만드는 문제입니다. 만약 각각의 경로를 오른쪽 아래로 한 칸씩 밀면 모든 경로가 겹치지 않게 만들 수 있고, 이 문제는 LGV Theorem을 이용해 해결할 수 있습니다.
LGV Theorem이 할 수 있는 일을 다시 한번 생각해 봅시다.
간선에 가중치가 있는 DAG에서, 어떤 경로 $P$ 위의 간선들의 가중치 곱을 $w(P)$, 모든 $a \rightarrow b$ 경로들의 $w(P)$ 의 합을 $e(a, b)$라고 정의합시다. $n$개의 시작점 $a_i$와 $n$개의 도착점 $b_i$가 주어졌을 때, 서로 점을 공유하지 않는 $n$개의 경로를 이용해 각 시작점과 도착점을 이대일 대응시키는 모든 경우에서 $w(P)$의 곱의 합은 행렬 $M(i, j) = e(a[i], b[j])$의 determinant와 동일하다는 정리입니다.
따라서 $A(R, C) = V$ 조건이 없으면 모든 간선의 가중치를 1로 둔 다음 LGV Theorem을 이용해 경우의 수를 셀 수 있는 것입니다.
다시 $A(R, C) = V$ 조건을 가져옵시다. $(R, C)$의 왼쪽 위에 $V-1$개의 경로가 지나가는 경우의 수를 구해야 합니다. LGV Theorem 자체를 변형하는 것은 어렵기 때문에, 간선의 가중치를 적당히 잘 잡아서 정답을 구하는 방법을 찾아야 합니다.
$R = C$이면 왼쪽 위에 있는 경로는 항상 $(R-1, C-1), (R-2, C-2), (R-3, C-3), \cdots$ 와 같은 점을 지나고, $R \neq C$이더라도 비슷하게 각 경로마다 정확히 하나만 포함되고, 각 점은 최대 한 개의 경로에 포함되는 점 집합을 구할 수 있습니다. 즉, 왼쪽 위로 $V-1$개의 경로가 지나간다는 것은 점 집합에서 $V-1$개의 점을 사용한다는 것을 의미합니다.
어떤 미지수 $x$를 잡아서, 점 집합으로 들어가는 간선의 가중치를 $1$, 나가는 간선의 가중치를 $x$라고 합시다. LGV Theorem을 이용해 determinant를 구하면 어떤 다항식이 나올 텐데, 이 다항식에서 $x^k$의 계수는 $k$개의 점을 사용하는 경우의 수를 의미합니다. 따라서 우리는 이 다항식을 구하면 됩니다.
다항식을 원소로 하는 행렬의 determinant를 구하는 것은 너무 비효율적이므로 다른 방법을 생각해야 합니다. 이 다항식의 차수가 $K$라는 것을 알고 있기 때문에 $x = 0, 1, 2, \cdots, K$일 때의 함숫값을 알면 다항식을 확정지을 수 있습니다.
$x$가 어떤 수로 고정되어 있을 때 $f(x)$를 구하는 것은 단순히 행렬의 determinant를 구하는 것이므로 가우스 소거법을 이용해 $O(K^3)$ 시간에 구할 수 있습니다. $O(K^4)$ 시간에 $K+1$개의 $(x_i, y_i)$ 쌍을 구했다면 Lagrange Interpolation을 이용해 다항식을 복원할 수 있습니다. $O(K \log^2 K)$에 할 수도 있지만 이 문제는 $O(K^2)$에 interpolate해도 충분합니다.