题意
某人在直线上走,直线上有若干格子,起点是1号格,每次这个人都有p概率走1格,1-p概率走二格,有一些格子有地雷,走上去就被爆了,所以要你求你能安全走到终点(可以看成是站在n+1号格)上概率。
思路
每一个格子的概率都可以通过它前两个的格子的概率推出来,这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么?快速幂。
所以这个题我们用快速幂来做。
dp方程其实都不叫dp,叫递推,大概长这个样子:
直接矩阵乘法模版+快速幂就行。
处理地雷的话,你就先走到地雷那里,停一下,把地雷格的dp值抹成0,然后继续往下走,走到下一个地雷,最后走到终点。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; const int N = 2; int n; struct Mat { double mat[N][N]; }; Mat operator * (Mat a, Mat b) { Mat c; memset(c.mat, 0, sizeof(c.mat)); int i, j, k; for(k = 0; k < N; ++k) { for(i = 0; i < N; ++i) { for(j = 0; j < N; ++j) { c.mat[i][j] += a.mat[i][k] * b.mat[k][j]; } } } return c; } Mat operator ^ (Mat a, int k) { Mat c; int i, j; for(i = 0; i < N; ++i) for(j = 0; j < N; ++j) c.mat[i][j] = (i == j); //初始化为单位矩阵 for(; k; k >>= 1) { if(k&1) c = c*a; a = a*a; } return c; } int main(){ while(cin >> n){ double p = 0; cin >> p; vector<double> mine; mine.push_back(0); for(int i = 1;i <= n;i++){ int tmp = 0; cin >> tmp; mine.push_back(tmp); } sort(mine.begin(),mine.end()); Mat a,b; double dn = 1; for(int i = 1;i < mine.size();i++){ a.mat[0][0] = p; a.mat[0][1] = 1-p; a.mat[1][0] = 1; a.mat[1][1] = 0; Mat c = a^(mine[i]-mine[i-1]); b.mat[0][0] = 0; b.mat[0][1] = 0; b.mat[1][0] = dn; b.mat[1][1] = 0; Mat d = c * b; dn = d.mat[1][0]; } printf("%.7f\n",dn); } return 0; } |