schindlerlee原创，禁止转载和用于商业用途
刚比赛完，先贴代码
1 /*
2 * SOUR:pku 3744
3 * ALGO:compulicted
4 * DATE: 2009年 08月 23日 星期日 12:37:44 CST
5 * COMM:3
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 #define inf 0x7fffffff
14 #define debug 1
15 double p;
16 int mine[26], n;
17
18 struct M {
19 double v11, v12, v21, v22;
20 M operator*( M b)
21 {
22 M c;
23 c.v11 = v11 * b.v11 + v12 * b.v21;
24 c.v12 = v11 * b.v12 + v12 * b.v22;
25 c.v21 = v21 * b.v11 + v22 * b.v21;
26 c.v22 = v21 * b.v12 + v22 * b.v22;
27 return c;
28 }
29
30 M operator*( double c)
31 {
32 v11 *= c, v12 *= c;
33 v21 *= c, v22 *= c;
34 return *this;
35 }
36 } unit,self;
37
38
39 M f(int t)
40 {
41 if (t == 0) {
42 M a;
43 a.v11 = 1, a.v12 = 0;
44 a.v21 = 0, a.v22 = 1;
45 return a;
46 }
47 if (t == 1) {
48 return unit;
49 }
50 if (t % 2 == 0) {
51 M tmp = f(t / 2);
52 return tmp * tmp;
53 }
54 M tmp = f(t / 2);
55 return tmp * tmp * unit;
56 }
57
58 /*
59 f(n) { p ,1-p } f(n-1)
60 f(n-1) = { 1 , 0 } * f(n-2)
61 * */
62 int main()
63 {
64 int i, j;
65 while (scanf("%d %lf", &n, &p) == 2) {
66 unit.v11 = p, unit.v12 = 1 - p;
67 unit.v21 = 1, unit.v22 = 0;
68
69 self.v11 = 1, self.v12 = 0;
70 self.v21 = 0, self.v22 = 1;
71
72 bool flag = false;
73 for (i = 0; i < n; i++) {
74 scanf("%d", mine + i);
75 }
76 sort(mine, mine + n);
77 n = unique(mine, mine + n) - mine;
78 for (i = 1; i < n; i++) {
79 if (mine[i] - mine[i - 1] == 1) {
80 flag = true;
81 break;
82 }
83 }
84 if (flag || mine[0] == 1) {
85 printf("%.7f\n", 0.0);
86 continue;
87 }
88 int t = 1;
89 M res = self, tmp;
90 for (i = 0; i < n; i++) {
91 tmp = f(mine[i] - 1 - t);
92 t = mine[i] + 1;
93 res = res * tmp * (1 - p);
94 res.v12 = 0; //跳地雷
95 }
96 if(res.v11 <= 0) {
97 printf("%.7f\n", 0.0);
98 }else {
99 printf("%.7f\n", res.v11);
100 }
101 }
102 return 0;
103 }
104