求める確率を$p_n$とします。$n<m$の時は前問と同じ解法で求めます。 以下では$n\geq m$の場合の解法について解説します。

${\bm v}_i=\left(\begin{array}{c}p_i\\p_{i+1}\\ \vdots \\p_{i+m-1}\end{array}\right), {\bm P}=\left(\begin{array}{cccccc}0&1&0&\cdots&\cdots&0\\0&0&1&0&\cdots&0\\0&0&0&\ddots&\cdots&\vdots\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&\cdots&\cdots&\cdots&\cdots&1\\1/m&1/m&\cdots&\cdots&\cdots&1/m\end{array}\right)$ （ただし、${\bm P}$は$m$次正方行列とします）とおくと、${\bm v}_{i+1}={\bm P}{\bm v}_i$が成立します。よって、$p_n$は${\bm P}^n{\bm v}_0$の第0成分に等しいです（ただし、$p_0=1$とします）。

${\bm v}_0$を求めるには$p_0,p_1,\cdots p_{m-1}$をすべて求める必要があるので、この部分の計算量は前問の解説より$O(m)$となります。また、行列乗算の計算量は$O(m^3\log n)$となります。 よって、全体の計算量は$O(m^3\log n)$となるので、十分時間内に間に合います。

質問・誤りがある場合

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