BOJ 12735 Boat

마지막으로 뽑은 원소의 인덱스가 $x$이고 그 값이 $y$일 때, 그러한 경우의 수를 $f(x, y)$라고 합시다. 편의상 아무것도 뽑지 않은 경우를 $f(0, 0) = 1$, $a_0 = b_0 = 0$으로 두면 다음이 성립합니다.

그리고 $s(x, y) = \sum_{i=0}^{x} \sum_{j=0}^{y} f(i,j)$로 정의하면 $f(x, y) \neq 0$인 경우 $f(x, y) = s(x-1, y-1)$이 됩니다.

그러나 $y$가 $10^9$까지 커질 수 있는 상황이므로, 특정 상황을 건너뛰어서 계산할 아이디어가 필요합니다.

$1 \le x \le N$에 대해 $f(x, y_1)$을 모두 알고 있고, $y_1 \le y \le y_2$에서 $f(x, y) \neq 0$인 $x$의 집합이 $x_1, x_2, \cdots$로 모두 동일하다면, DP 테이블의 $y_1$번째 줄에서 $y_2$번째 줄로 다음과 같이 건너뛸 수 있습니다.

그리고 $f(x, y_2) = 0$인 경우, $x$ 이하이면서 $f(x_i, y_2) \neq 0$인 가장 큰 $x_i$에 대해 다음이 성립합니다.

이들을 종합하면, $x$의 집합이 바뀌는 시점들을 찾아서 그러한 구간은 한 줄씩 전이해주고 그렇지 않은 구간은 $\mathcal{O}(N^2)$의 시간에 건너뜀으로써 $\mathcal{O}(N^3)$ 시간에 답을 구할 수 있습니다.