$i\geq m$の時、$i$マス目に止まるのは、

• $(i-m)$マス目に止まった直後に$m$を出した場合
• $(i-m+1)$マス目に止まった直後に$(m-1)$を出した場合 ...
• $(i-1)$マス目に止まった直後に$1$を出した場合

の$m$パターンあり、これらは全て排反事象である。

また、$1\leq i\leq m-1$の時、$i$マス目に止まるのは、

• $0$マス目に止まった（則ち、スタート時）直後に$i$を出した場合
• $1$マス目に止まった直後に$(i-1)$を出した場合 ...
• $(i-1)$マス目に止まった直後に$1$を出した場合

の$i$パターンあり、これらは全て排反事象である。

よって、$i$マス目に止まる確率を$p_i$とすると、$p_i=\displaystyle{\frac{1}{m}}{\displaystyle{\sum_{j=\min(0,i-m)}^{i-1}{p_j}}}$が成立する。

尺取法により、$1\leq i\leq n$を満たす各$i$について$p_i$を$O(1)$で計算できるので、計算量は$O(n)$となる。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378