描述
题解
分段 + 概率 DP + 矩阵加速。
首先,题目给了雷的数目至多只有十个,不算多,可以将全程进行分段,保证每段只有一个雷或者多个雷在一个位置,并且雷的位置都是段尾。
分段后,每一段之间都是独立的,求出安全通过每一段的概率,最后根据乘法原理即可求出整段的概率。
我们拿第一段来说,第一段是 1∼x[0] ,在 x[0] 处有雷,安全通过就是到达 x[0]+1 的位置。
设 dp[i] 表示安全到达 i 点的概率,那么
那么问题来了,雷怎么处理?斐波那契数列的矩阵加速求法是不考虑障碍的,所以我们需要特别考虑 dp[x[0]+1] 的概率,这里我们很容易理解, dp[x[0]+1]=1−dp[x[0]] ,也就是说安全通过的概率为没有踩到雷的概率,也就是 1−dp[x[0]] 。
初始,设置每一段开始的概率为 1.0 ,这样才能利用乘法原理得到正确答案。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 15;
struct Matrix
{
double mat[2][2];
};
Matrix mul(Matrix a, Matrix b)
{
Matrix ret;
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
ret.mat[i][j] = 0;
for (int k = 0; k < 2; k++)
{
ret.mat[i][j] += a.mat[i][k] * b.mat[k][j];
}
}
}
return ret;
}
Matrix QPow_M(Matrix a, int n)
{
Matrix ret;
memset(ret.mat, 0, sizeof(ret.mat));
for (int i = 0; i < 2; i++)
{
ret.mat[i][i] = 1;
}
Matrix tmp = a;
while (n)
{
if (n & 1)
{
ret = mul(ret, tmp);
}
tmp = mul(tmp, tmp);
n >>= 1;
}
return ret;
}
int n;
double p;
int x[MAXN];
int main(int argc, const char * argv[])
{
while (cin >> n >> p)
{
for (int i = 0; i < n; i++)
{
scanf("%d", x + i);
}
sort(x, x + n);
double ans;
Matrix m, t;
m.mat[0][0] = p;
m.mat[0][1] = 1 - p;
m.mat[1][0] = 1;
m.mat[1][1] = 0;
t = QPow_M(m, x[0] - 1);
ans = (1 - t.mat[0][0]);
for (int i = 1; i < n; i++)
{
if (x[i] == x[i - 1])
{
continue;
}
t = QPow_M(m, x[i] - x[i - 1] - 1);
ans *= (1 - t.mat[0][0]);
}
printf("%.7lf\n", ans);
}
return 0;
}