[BOJ] 9341. ZZ

starbow·2025년 8월 18일

PS/CP

목록 보기

23/25

각 테스트 케이스 $a \, b \, c \, d$ 가 주어질 때 $ZZ(c, d)$ 를 구하면 되는 문제입니다. $ZZ$ 의 점화식은 아래와 같습니다.

\begin{aligned} &ZZ(0, 1) = a \\ &ZZ(0, 2) = b \\ &ZZ(0, k) = ZZ(0, k - 1) + ZZ(0, k - 2); k \geq 3 \\ &ZZ(i, k) = \displaystyle\sum_{j = 1}^{k}{ZZ(i - 1, j)}; i \geq 1, k \geq 1 \\ \end{aligned}

위 점화식을 이리저리 가지고 놀다보면 다음 식을 얻을 수 있습니다.

\begin{aligned} &ZZ(1, k) = ZZ(0, k + 2) - \binom{k}{0} \cdot b \\ &ZZ(2, k) = ZZ(1, k + 2) - \binom{k + 1}{1} \cdot b - \binom{k + 1}{0} \cdot a \\ &\cdots \end{aligned}

뭔가 일반화가 가능할것 같이 생겼습니다. 진짜 일반화가 될까요? 아래 내용을 증명해 보겠습니다.

Theorem. $ZZ(c, d) = ZZ(c - 1, d + 2) - \binom{d + c - 1}{c - 1} \cdot b - \binom{d + c - 1}{c - 2} \cdot a$

일단 $c = 1$ 일때는 직접 계산해보면 어렵지 않게 보일 수 있습니다.

$c = 1, 2, \cdots, k - 1$ 일때 Theorem이 성립 한다고 가정해 보겠습니다.

\begin{aligned} ZZ(k, d) &= ZZ(k - 1, 1) + \cdots + ZZ(k - 1, d) \\ &= ZZ(k - 2, 1) - \binom{k - 3}{k - 3} \cdot a \\ &+ ZZ(k - 2, 2) - \binom{k - 2}{k - 2} \cdot b - \binom{k - 2}{k - 3} \cdot a \\ &+ ZZ(k - 2, 3) - \binom{k - 1}{k - 2} \cdot b - \binom{k - 1}{k - 3} \cdot a \\ &+ ZZ(k - 2, 4) - \binom{k}{k - 2} \cdot b - \binom{k}{k - 3} \cdot a \\ &+ \cdots \\ &+ ZZ(k - 2, d + 2) - \binom{k + d - 2}{k - 2} \cdot b - \binom{k + d - 2}{k - 3} \cdot a \\ &= ZZ(k - 1, d + 2) - \binom{k + d - 1}{k - 1} \cdot b - \binom{k + d - 1}{k - 2} \cdot a \end{aligned}

즉, $c = 1, 2, \cdots, k - 1$ 일때 Theorem이 성립하면 $c = k$ 일때도 성립한다는 사실을 알 수 있고 수학적 귀납법에 의하여 Theorem이 증명되었습니다.

이제 Theorem을 가지고 각 테스트 케이스를 해결하면 됩니다. 최종적으로 $ZZ(0, d + 2c)$ 와 $2c$ 개의 Combination을 계산하면 됩니다.
각 Combination은 $1!$ 부터 $(c-1)!$ 까지의 역원을 미리 전처리 해놓으면 $O(c)$ 에 계산할 수 있고 $ZZ(0, d + 2c)$ 는 $O(\log{(d + 2c)})$ 에 계산할 수 있습니다.