题目

{% fold 点击显/隐题目 %}

题解

不考虑地雷的情况下,可以很容易得到递推式:
dp(i) = p*dp(i-1)+(1-p)*dp(i-2)

然而由于距离可以达到100000000,直接去计算需要非常多的内存

根据概率的知识,可以知道,能够通过每一个雷区的概率等于1-踩雷的概率
而通过整个区域的概率就是通过每个雷区的概率的乘积

根据雷区的位置,可以把整个区域分成多段,每一段有且仅有一个地雷
计算每一段的概率即可

不过每一段的长度也有可能是非常长的,要解决它有两种思路:
高中数学优化和高等数学优化

对于 {% raw %}$a_n = p \times a_{n-1}+(1-p) \times a_{n-2}${% endraw %} ,求其通项公式
化简步骤如下:

{% raw %}
\begin{align*} a_n &= p \times a_{n-1} + (1-p) \times a_{n-2} \\ a_n &= (1-(1-p)) \times a_{n-1} + (1-p) \times a_{n-2} \\ a_n &= a_{n-1} - (1-p) \times a_{n-1} + (1-p) \times a_{n-2} \\ a_n - a_{n-1} &= -(1-p) (a_{n-1} - a_{n-2}) \\ \end{align*}
{% endraw %}

这时,已经可以看出等号两边的结构相等了
设一个辅助数列
{% raw %}
$$
\begin{align*}
令 b_n &= a_{n+1}-a_{n} \
\
有 b_n &= (p-1) \times b_{n-1} \
可得 b_n &= b_1 \times (p-1)^n-1 \
b_{n-1} &= b_1 \times (p-1)^{n-2} \
b_{n-1} &= a_{n} - a_{n-1}\
\
a_{n} - a_{n-1} &= (a_2 - a_1) \times (p-1)^{n-2} \
a_{n-1} - a_{n-2} &= (a_2 - a_1) \times (p-1)^{n-3} \
& ...\
a_{2} - a_{1} &= (a_2 - a_1) \times (p-1)^{0} \
\
a_{n} - a_{1} &= \sum_{i=0}^{n-2} ((a_2 - a_1) \times (p-1)^i) \
a_{n} - a_{1} &= (a_2 - a_1) \times \sum_{i=0}^{n-2} (p-1)^i) \
a_{n} - a_{1} &= (a_2 - a_1) \times \frac {1 \times (1-(p-1)^{n-1})} {1-(p-1)} \
a_{n} &= a_{1} + (a_2 - a_1) \times \frac {1-(p-1)^{n-1}} {2-p} \

\
其中 a_1 &= 1 , a_2 = p\
a_{n} &= 1 + (p-1) \times \frac {1-(p-1)^{n-1}} {2-p} \

\end{align*}
$$
{% endraw %}

也即,我们有了dp的通项公式
dp[i] = 1 + (p-1)*(1-(p-1)^(n-1)/(2-p))

平方部分使用快速幂计算即可

当然,也可以使用高等数学部分的矩阵乘法

{% raw %}$
\begin{pmatrix}
p & 1-p\
1 & 0
\end{pmatrix}
\times
\begin{pmatrix}
dp[i] \
dp[i-1]
\end{pmatrix}

\begin{pmatrix}
p \times dp[i] + (1-p) \times dp[i-1] \
dp[i]
\end{pmatrix}

\begin{pmatrix}
dp[i+1] \
dp[i]
\end{pmatrix}
${% endraw %}

那么可以推出dp[i]的表达式为
{% raw %}$
\begin{pmatrix}
dp[i]\
dp[i-1]
\end{pmatrix}

\begin{pmatrix}
p & 1-p\
1 & 0
\end{pmatrix} ^ {n-2}
\times
\begin{pmatrix}
p\
1
\end{pmatrix}
${% endraw %}

使用快速矩阵幂计算即可,需要注意两个雷紧挨着的时候的情况

代码

{% fold 点击显/隐递推方法代码 %}```cpp Scout YYF递推 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 15;

double pow(double a, int n) {
if (n == 0)
return 1.0;
if (n == 1)
return a;
double ans = pow(a, n / 2);
ans = ans * ans;
if (n & 1)
ans *= a;
return ans;
}
double f(int n,double p){
return 1 + (p - 1) * (1 - pow(p - 1, n - 1)) / (2 - p);
}

int mines[maxn];

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);
int n;
double p;
while (cin >> n >> p) {
mines[0] = 0;
for (int i = 1; i <= n; i++)
cin >> mines[i];

    sort(mines + 1, mines + 1 + n);

    double ans = 1;
    for (int i = 1; i <= n; i++) {
        int dis = mines[i] - mines[i - 1];

        double dp = f(dis,p); 
        //cout <<"\t "<<dis<<" "<< dp<<endl;
        ans *= (1 - dp);
    }

    cout << fixed << setprecision(7) << ans << endl;
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}

{% endfold %}

{% fold 点击显/隐矩阵方法代码 %}```cpp Scout YYF矩阵  https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <set>
using namespace std;

const int maxn = 15;

class Matrix {
  public:
    static const int LINE = 2; //行列数
    double matrix[LINE][LINE];

    Matrix() {
        for (int i = 0; i < LINE; i++)
            for (int j = 0; j < LINE; j++)
                matrix[i][j] = 0;
    }

    Matrix operator*(Matrix rhs) { return mul(*this, rhs); }
    Matrix operator^(int n) { return pow(*this, n); }

    static Matrix mul(Matrix a, Matrix b) {
        Matrix ans;
        for (int i = 0; i < LINE; i++)
            for (int j = 0; j < LINE; j++) {
                ans.matrix[i][j] = 0;
                for (int k = 0; k < LINE; k++)
                    ans.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j];
            }
        return ans;
    }

    static Matrix pow(Matrix a, int n) {
        if (n == 0) {
            Matrix E;
            for (int i = 0; i < LINE; i++)
                E.matrix[i][i] = 1;
            return E;
        }
        if (n == 1)
            return a;
        Matrix ans = pow(a, n / 2);
        ans = ans * ans;
        if (n & 1)
            return ans * a;
        return ans;
    }
    void print() {
        for (int i = 0; i < LINE; i++) {
            printf("|");
            for (int j = 0; j < LINE; j++)
                printf("%f ", matrix[i][j]);
            printf("|\n");
        }
        printf("\n");
    }
};

int mines[maxn];

int main() {
#ifdef debug
    freopen("in.txt", "r", stdin);
    int START = clock();
#endif
    cin.tie(0);
    cin.sync_with_stdio(false);

    int n;
    double p;
    while (cin >> n >> p) {
        mines[0] = 0;
        for (int i = 1; i <= n; i++)
            cin >> mines[i];

        sort(mines + 1, mines + 1 + n);

        double ans = 1;
        for (int i = 1; i <= n; i++) {
            int dis = mines[i] - mines[i - 1];

            if (dis == 1) {
                ans = 0;
                break;
            }

            Matrix dp, pro;
            dp.matrix[0][0] = p;
            dp.matrix[1][0] = 1;

            pro.matrix[0][0] = p;
            pro.matrix[0][1] = 1 - p;
            pro.matrix[1][0] = 1;

            dp = Matrix::pow(pro, dis - 2) * dp;

            dp.print();

            ans *= (1 - dp.matrix[0][0]);
        }

        cout << fixed << setprecision(7) << ans << endl;
    }

#ifdef debug
    printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
    return 0;
}

{% endfold %}