BOJ 13178. 목공
문제 해석
정수 \(X\)와, \(X\)의 값을 감소시키는 연산이 있다. 이 연산을 하려면 \(X\)가 \(N\) 이상이어야 하고, 감소하는 양은 확률적으로 결정되며 매번 독립이다. 음이 아닌 정수 \(q_0, \cdots, q_{N-1}\)가 존재해서, \(X\)에 연산을 1회 가하여 \(X-N+i\ (0 \le i \lt N)\)가 될 확률은 \(\frac{q_i}{\sum q_*}\)와 같다. \(X\)의 현재 값이 \(M\)일 때, \(X\)를 \(N\)보다 작게 만들기 위해 필요한 연산 횟수의 기댓값을 구하라.
접근
기댓값에 대한 점화식이 세워질 것임을 어렵지 않게 볼 수 있다. \(X\)의 초기값이 \(m\)일 때의 기댓값을 \(E_m\)이라 하면 점화식은 아래와 같다.
\[E_m = \begin{cases} 1 + \frac{q_{N-1}}{\sum q_*} E_{m-1} + \frac{q_{N-2}}{\sum q_*} E_{m-2} + \cdots + \frac{q_0}{\sum q_*} E_{m-N} & ; & m \ge N\\ 0 & ; & m \lt N \end{cases}\]\(N\)과 \(M\)이 둘 다 상당히 크기 때문에 Kitamasa나 Bostan-Mori를 쓰고 싶지만 점화식이 non-homogeneous해서 이대로는 쓸 수 없으니, index를 \(1\)씩 내린 식을 빼서 상수항을 없애 준다. 대신 점화식의 order는 하나 올라간다.
바뀐 점화식은 아래와 같다.
\[E_m = \begin{cases} \left( \frac{q_{N-1}}{\sum q_*} + 1 \right) E_{m-1} + \left( \frac{q_{N-2} - q_{N-1}}{\sum q_*} \right) E_{m-2} + \cdots + \left( \frac{q_0 - q_1}{\sum q_*} \right) E_{m-N} - \left( \frac{q_0}{\sum q_*} \right) E_{m-N-1} & ; & m \gt N\\ 1 & ; & m = N\\ 0 & ; & m \lt N \end{cases}\]mod 값이 int 최댓값의 절반을 넘는다는 사실에 주의하자. Modular arithmetic 구현 시 부호 없는 32비트 또는 64비트 정수형이 필요하다.