問題

提出解答

$6$ 面体の各目が同様に確からしく出るサイコロがある. 最初, $X=1$ である. 以下の行動を $X \lt N$ となる限り行う.

行動終了後, $X=N$ となる確率を求めよ.

正の有理数 $n$ に対して, $\operatorname{Prob}(n)$ で $X=n$ とできる確率とする.

まず, $\operatorname{Prob}(0)=1$ であり, $n$ が整数ではないならば, $\operatorname{Prob}(n)=0$ である.

$2$ 以上の整数 $n$ に対して, 各目で場合分けすることにより,

$\displaystyle \operatorname{Prob}(n)=\dfrac{1}{6} \sum_{a=1}^6 \operatorname{Prob} \left(\dfrac{N}{a} \right)$

となる.

ここで, 左辺と右辺に $f(n)$ が現れているが, 整理することによって,

$\displaystyle \operatorname{Prob}(n)=\dfrac{1}{5} \sum_{a=2}^6 \operatorname{Prob} \left(\dfrac{N}{a} \right)$

となる.

$1,2,3,4,5,6$ に現れる素因数は $2,3,5$ である. そして,

$\left \lceil \log_2 N \right \rceil \leq 60, \quad \left \lceil \log_3 N \right \rceil \leq 38, \quad \left \lceil \log_5 N \right \rceil \leq 26$

となるから, $\operatorname{Prob}(N)$ の計算に必要な引数のうち, 整数になるのは高々 $60 \times 38 \times 26=59280$ 個であり, 深さは高々 $60+38+26=104$ である.

よって, 整数でない $n$ における $\operatorname{Prob}(n)$ はすぐに $0$ を返すようにメモ化再起を計算することによって, $\operatorname{Prob}(N)$ を $O((\log N)^3)$ 時間で計算できる.