抄袭自https://cloud.tencent.com/developer/article/1340113
输入n表示共有n个地雷(0<n<=10),并且输入每个地雷所在的位置ai(ai为不大于108的正整数)。现在求从1号位置出发越过所有地雷的概率。用两种行走方式:①走一步②走两步(不会踩爆中间那个雷)。这两个行为的概率分别为p和(1-p)。
说一个和上面那人不太一样的做法
首先暴力肯定是$fi$表示到第$i$个位置还活着的概率
发现$n <= 10$,所以中间的用矩阵快速幂优化
上面那人是用$1 -$死了的概率
我们也可以直接算出走到雷前面的概率,这时候只能走两步,所以再乘$(1 - P)$
两个雷相邻的情况需要特判
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1051;
int N;
double P;
int a[MAXN];
struct Matrix {
double m[5][5];
void init(double p) {
m[1][1] = p; m[1][2] = 1 - p;
m[2][1] = 1; m[2][2] = 0;
}
Matrix operator * (const Matrix &rhs) const {
Matrix c = {};
for(int k = 1; k <= 2; k++)
for(int i = 1; i <= 2; i++)
for(int j = 1; j <= 2; j++)
c.m[i][j] += m[i][k] * rhs.m[k][j];
return c;
}
};
Matrix fastpow(Matrix a, int p) {
Matrix base = {};
for(int i = 1; i <= 2; i++) base.m[i][i] = 1;
while(p > 0) {
if(p & 1) base = base * a;
a = a * a; p >>= 1;
}
return base;
}
int main() {
while(scanf("%d %lf", &N, &P) != EOF) {
for(int i = 1; i <= N; i++) scanf("%d", &a[i]);
sort(a + 1, a + N + 1);
double p = 1; int now = 1;
for(int i = 1; i <= N; i++) {
if(a[i] == a[i - 1] + 1) {p = 0; break;}
Matrix cur; cur.init(P);
cur = fastpow(cur, a[i] - a[i - 1] - 2);
p *= cur.m[1][1] * (1 - P);
}
printf("%.7lf\n", p);
}
return 0;
}
/*
2 0.5
2 3
1 0.5
2
*/