[latexpage]

题意:特工YYF潜入敌方根据地,历经千辛万苦后他站在了一条地雷路的第一格。伴随着音乐和鼓点,他每一步有p的概率往前走一格,(p-1)的概率跳过一格到达第二格。求他生还的概率。地雷少于11个,但位置可能达到108大小。

思路:因为YYF不被某个地雷炸死当且仅当他前一秒站在地雷前,后一秒跳到了地雷后,所以我们可以把地雷两两间的路抽出来,设两个地雷间的路从起点到终点的生还概率为x,那么总生还概率为 ∏pi

对于长度为l的路,令f[i]为从第i个格子走到末端的生还概率,那么$f[i]=f[i+1]×p+f[i+2]×(1-p)$

特殊的,f[l]=1-p(只有跳过后一个格子他才暂时安全)

于是,现在我们需要在很短的时间内求出某种长度的路的生还几率。

注意到,f[i]的递推方式很像斐波那契数列,所以我们可以利用矩阵乘法来求f[i]

\begin{equation} \label{eq:poly}
   \begin{Bmatrix}
f(i) \\
f(i+1)
\end{Bmatrix}=
\begin{Bmatrix}
f(i+1) \\
f(i+2)
\end{Bmatrix}*
\begin{Bmatrix}
p & 1-p \\
1 & 0
\end{Bmatrix}
\end{equation}