No.301

No.75 と同様の問題であるが, $N$ の範囲が大きい.

$N$ がある程度小さいときは, No.75 と同様に計算する.

このとき, 高速化のために $E(x)$ を求める漸化式を行列を使って以下のように表す.

$$\begin{eqnarray} \left( \begin{array}{c} E(x) \\ E(x+1) \\ E(x+2) \\ E(x+3) \\ E(x+4) \\ E(x+5) \\ 1 \end{array} \right) = \left( \begin{array}{cccccccc} 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1 \\ 1 & & & & & & \\ & 1 & & & & & \\ & & 1 & & & & \\ & & & 1 & & & \\ & & & & 1 & & \\ & & & & & & 1 \end{array} \right) \left( \begin{array}{c} E(x+1) \\ E(x+2) \\ E(x+3) \\ E(x+4) \\ E(x+5) \\ E(x+6) \\ 1 \end{array} \right) \end{eqnarray}$$

あとは繰り返し2乗法で計算すれば, $E(x)$ を高速に計算できる.

$N$ がある程度より大きい場合であるが, 答えは $N + 5/3$ に収束していくことが確認できる.

$N$ が $150$ より大きい場合はこの計算式で誤差は問題ない.