2/2

PKU 3744

ある場所からnステップ先の場所に行ける確率をf(n)とすると明らかに次の式が成り立つ。

f(n) = pf(n-1) + (1-p)f(n-2)

これの特性方程式は

x^2 - px - 1 + p = 0

これを解くと

x = 1, p-1

よって

f(n) = c₁ + c₂(p-1)ⁿ

と書ける。f(0) = 1, f(1) = p は明らかなので

c₁ + c₂ = 1

c₁ + c₂(p-1) = p

これを連立して解けば

(c₁, c₂) = (1/(2-p), (p-1)/(p-2))

したがって

f(n) = ((p-1)ⁿ⁺¹-1)/(p-2)

これが分かれば f(n) は O(log n) で計算できる(累乗の計算)ので後はやるだけ。