【题解】Scout YYF I (POJ3744) 概率 DP+矩阵快速幂

[latexpage]

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

思路：因为 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}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MX 12
using namespace std;
double p;
int bom[MX],n;
void input(){
    for(int i=1;i<=n;i++)scanf("%d",&bom[i]);
    sort(bom+1,bom+n+1);
}
void mul(double dist[][3],double a[][3],double b[][3]){
    double now[3][3];
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)now[i][j]=0;
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)now[i][j]+=a[k][j]*b[i][k];
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)dist[i][j]=now[i][j];
}
void quickp(double dist[][3],double src[][3],int t){
    double ans[3][3],now[3][3];
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)now[i][j]=src[i][j];
    ans[1][1]=ans[2][2]=1,ans[2][1]=ans[1][2]=0;
    while(t>=1){
        if(t%2==1)mul(ans,now,ans);
        mul(now,now,now);
        t/=2;
    }
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)dist[i][j]=ans[i][j];
}
double work(int len){
    if(len==0)return 0;
    double sc[3][3],f[3][3];
    sc[1][1]=p,sc[1][2]=1-p,sc[2][1]=1,sc[2][2]=0,f[1][1]=1-p,f[1][2]=0,f[2][1]=0,f[2][2]=0;
    quickp(sc,sc,len-1);
    mul(f,f,sc);
    return f[1][1];
}
int main(){
    double ans;
    while(cin>>n>>p,ans=1){
        input();
        for(int i=1;i<=n;i++)if(bom[i]!=bom[i-1])ans*=(work(bom[i]-bom[i-1]-1));
        printf("%.7f\n",ans);
    }
    return 0;
}