poj3744_矩阵快速幂

题意：起点为1，走一步的概率为p，走两步的概率为1-p,

有n个地雷，给出地雷所在的位置，求安全避过所有地雷的概率

思路：注意特判地雷在1位置和两个地雷相隔单位1的情况的结果都是0

设x[i]为走距离为i时的概率

安全距离为a的概率= x[a - 1] * p + x[a - 2] * (1 - p)

知道这个通式后就用矩阵快速幂啦

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <queue>
10 #include <vector>
11 #define INF 0x3f3f3f3f
12 using namespace std;
13 
14 int n, x[20];
15 double p;
16 struct node{
17     double res[2][2];
18 };
19 node mul(node p, node l)
20 {
21     node t;
22     t.res[0][0] = p.res[0][0] * l.res[0][0] + p.res[0][1] * l.res[1][0];
23     t.res[0][1] = p.res[0][0] * l.res[0][1] + p.res[0][1] * l.res[1][1];
24     t.res[1][0] = p.res[1][0] * l.res[0][0] + p.res[1][1] * l.res[1][0];
25     t.res[1][1] = p.res[1][0] * l.res[0][1] + p.res[1][1] * l.res[1][1];
26     return t;
27 }
28 double juz(int x)
29 {
30     if(x == 0)
31         return 1;
32     if(x == 1)
33         return p;
34     x--;
35     node m, s;
36     memset(m.res, 0, sizeof(m.res));
37     for(int i = 0; i < 2; i++)
38         m.res[i][i] = 1;
39     s.res[0][0] = p, s.res[0][1] = 1 - p;
40     s.res[1][0] = 1, s.res[1][1] = 0;
41     while(x > 0)
42     {
43         if(x & 1)
44             m = mul(m, s);
45         s = mul(s, s);
46         x >>= 1;
47     }
48     return m.res[0][0] * p + m.res[0][1];
49 }
50 int main()
51 {
52     while(scanf("%d %lf", &n, &p) != EOF)
53     {
54         for(int i = 1; i <= n; i++)
55             scanf("%d", &x[i]);
56         sort(x + 1, x + n + 1);
57         double res = 1;
58         x[0] = 0;
59         for(int i = 1; i <= n; i++)
60         {
61             if(x[1] == 1 || x[i] == x[i - 1] + 1)
62             {
63                 res = 0;
64                 break;
65             }
66             if(x[i] == x[i - 1])
67                 continue;
68             res *= juz(x[i] - x[i - 1] - 2) * (1 - p);
69         }
70         printf("%.7f
", res);
71     }
72     return 0;
73 }

poj3744_矩阵快速幂

相关推荐