$poj\ 3744$

题目大意

区间$[1,10^9]$内有$n(n \leq 10)$个地雷$a_1 \dots a_n$，从$1$出发，每次走$1$或$2$步，走$1$步的概率是$p$，走$2$步的概率是$1-p$，求安全走出雷区的概率。

解

方程

$$ f_i= \left\{ \begin{array}{ll} 0 & \textrm{$i \in {a}$} \\ p \cdot f_{i-1} + (1-p) \cdot f_{i-2} & \textrm{else} \end{array} \right. $$

$n_0=2$，特判$1$处是否有地雷， $\mathbf{F(2)}= \left( \begin{array}{c} p & 1 \end{array} \right)$

$sort(a)$，构造矩阵$\mathrm{R}$，分段求解，$f_{a_n+1}$即为所求。

$$ \mathbf{R}= \left( \begin{array}{cc} p & 1 \\ 1-p & 0 \end{array} \right) $$

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)

using namespace std;
struct mat
{
    int n,m;
    double v[2][2];
    mat(){}
    mat(int a,int b):n(a),m(b)
    {
        memset(v,0,sizeof(v));
    }
    double *operator [] (int x)
    {
        return v[x];
    }
} r,s,t;
int n,a[11];
double p;

inline void operator *= (mat &a,mat b)
{
    double t[2];
    rep(i,0,a.n)
    {
        memset(t,0,sizeof(t));
        rep(j,0,a.m)
            rep(k,0,a.m)
                t[j]+=a[i][k]*b[k][j];
        memcpy(a[i],t,sizeof(t));
    }
}

int main()
{
    while (scanf("%d%lf",&n,&p)==2)
    {
        a[0]=2;
        rep(i,1,n)
            scanf("%d",a+i);
        sort(a+1,a+1+n);
        if (a[1]==1)
        {
            puts("0.0000000");
            continue;
        }
        r=mat(1,1),s=mat(0,1);
        r[0][0]=p,r[1][0]=1-p,r[0][1]=1;
        s[0][0]=p,s[0][1]=1;
        rep(i,1,n)
        {
            if (!s[0][0] && !s[0][1])
                break;
            t=r;
            for (int j=a[i]-a[i-1]; j; j>>=1,t*=t)
                if (j&1)
                    s*=t;
            s[0][0]=0;
        }
        printf("%.7f\n",s[0][0]*p+s[0][1]*(1-p));
    }
    return 0;
}