# Scout YYF I POJ - 3744（概率dp）

Description

YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy‘s base. After overcoming a series difficulties, YYF is now at the start of enemy‘s famous "mine road". This is a very long road, on which there are numbers of mines. At first, YYF is at step one. For each step after that, YYF will walk one step with a probability of p, or jump two step with a probality of 1-p. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the "mine road" safely.

Input

The input contains many test cases ended with EOF.
Each test case contains two lines.
The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step.
The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].

Output

For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.

Sample Input

```1 0.5
2
2 0.5
2 4```

Sample Output

```0.5000000
0.2500000

```  1 /*
2           .
3          ‘;;;;;.
4         ‘!;;;;;;!;`
5        ‘!;|&#@|;;;;!:
6       `;;!&####@|;;;;!:
7      .;;;!&@\$\$%|!;;;;;;!‘.`:::::‘.
8      ‘!;;;;;;;;[email protected]###&|;;|%!;!\$|;;;;|&&;.
9      :!;;;;[email protected]&%|;;;;;;;;;|!::!!:::;!\$%;!\$%`    ‘!%&#########@\$!:.
10      ;!;;!!;;;;;|\$\$&@##\$;;;::‘‘‘‘‘::;;;;|&|%@\$|;;;;;;;;;;;;;;;;!\$;
11      ;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;\$%`
12     `!!;;;;;;;;;;!|%%|!!;::;;|@##%|\$|;;;;;;;;;;;;!|%\$#####%;;;%&;
13     :@###&!:;;!!||%%%%%|!;;;;;||;;;;||!\$&&@@%;;;;;;;|\$\$##\$;;;%@|
14     ;|::;;;;;;;;;;;;|&&\$|;;[email protected]&\$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%.
15    `!!;;;;;;;!!!!;;;;;[email protected]@@&&&&&@\$!;!%|;;;;!||!;;;;;!|%%%!;;%@|.
16 %&&\$!;;;;;!;;;;;;;;;;;|\$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;\$##!
17 !%;;;;;;!%!:;;;;;;;;;;!\$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;\$&:
18 ‘:|@###%;:;;;;;;;;;;;;!%\$&&&&&&@@\$!;;;;;;;!!!;;;;;%&!;;|&%.
19  [email protected]|;;;;;;;;;;;;;;;;;;|%|\$&&\$%&&|;;;;;;;;;;;;!;;;;;!&@@&‘
20   .:%#&!;;;;;;;;;;;;;;!%|\$\$%%&@%;;;;;;;;;;;;;;;;;;;!&@:
21   .%\$;;;;;;;;;;;;;;;;;;|[email protected]&|;;;;;;;;;;;;;;;;;;;;%@%.
22     !&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#;
23      `%\$!;;;;;;;;;;;[email protected]|;;;;;;;;;;;;;;;;;;;;;;;;!%[email protected]#@|.
24        .|@%!;;;;;;;;;!\$&%||;;;;;;;;;;;;;;;;;!%[email protected]#|.
25            ;&\$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|.
26            |##\$|!;;;;;;::‘‘:;;;;;;;;;;;;;!%[email protected]#@;
27           ;@&|;;;;;;;::‘‘‘‘‘‘:;;;;;;;|\$&@###@|`
28         .%##@|;;;;:::‘‘‘‘‘‘‘‘‘‘::;!%&##\$‘
29       `\$##@[email protected]@&|!!;;;:‘‘‘‘‘::::;;;;;|&#%.
30     ;&@##&\$%!;;;;;;::‘‘‘‘‘‘‘‘::;!|%[email protected]#@&@@:
31      .%@&\$\$|;;;;;;;;;;:‘‘‘‘:‘‘‘‘::;;;%@#@@#%.
32     :@##@###@\$\$\$\$\$|;;:‘‘‘‘:;;!!;;;;;;!\$#@@#\$;`
33      `%@\$\$|;;;;;;;;:‘‘‘‘‘‘‘::;;;;|%\$\$|!!&###&‘
34      |##&%!;;;;;::‘‘‘‘‘‘‘‘‘‘‘‘::;;;;;;;[email protected]&:`!‘
35     :;[email protected]\$|;;;;;;;::‘‘‘‘‘‘‘‘‘‘‘:;;;;;;;;!%&@\$:                 [email protected]#\$‘
36       |##@@&%;;;;;::‘‘‘‘‘‘‘‘‘:;;;;;;;!%&@#@\$%:              ‘%%!%&;
37       |&%!;;;;;;;%\$!:‘‘‘‘‘‘‘:|%!;;;;;;;;|&@%||`            ‘%\$|!%&;
38       |@%!;;!!;;;||;:‘‘‘‘‘‘:;%\$!;;;;!%%%&#&%\$&:           .|%;:!&%`
39       [email protected]&%;;;;;;;||;;;:‘‘::;;%\$!;;;;;;;|&@%;!\$;          `%&%!!\$&:
40       ‘\$\$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!\$##;         !\$!;:!\$&:
41        |#&|;;;;;;!||;;;;;;;;!%|;;;;!\$##\$;;;;|%‘      `%\$|%%;|&\$‘
42         |&%!;;;;;;|%;;;;;;;;\$\$;;;;;;|&&|!|%&&;  .:%&\$!;;;:[email protected]!
43         `%#&%!!;;;;||;;;;;!\$&|;;;!%%%@&!;;;!!;;;|%!;;%@\$!%@!
44         !&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&\$;;;|&%;;;%@%`
45        ‘%|;;;;;;;;!!|\$|%&%;;;;;;;;;;|&#&|!!||!!|%[email protected]@|‘
46        .!%%&%‘`|\$;       :|\$#%|@#&;%#%.
47 */
48 #include <map>
49 #include <set>
50 #include <list>
51 #include <ctime>
52 #include <cmath>
53 #include <stack>
54 #include <queue>
55 #include <string>
56 #include <vector>
57 #include <cstdio>
58 #include <bitset>
59 #include <cstdlib>
60 #include <cstring>
61 #include <iostream>
62 #include <algorithm>
63 #define  lowbit(x)  x & (-x)
64 #define  mes(a, b)  memset(a, b, sizeof a)
65 #define  fi         first
66 #define  se         second
67 #define  pii        pair<int, int>
68 #define  INOPEN     freopen("in.txt", "r", stdin)
69 #define  OUTOPEN    freopen("out.txt", "w", stdout)
70
71 typedef unsigned long long int ull;
72 typedef long long int ll;
73 const int    maxn = 1e5 + 10;
74 const int    maxm = 1e5 + 10;
75 const int    mod  = 1e9 + 7;
76 const ll     INF  = 1e18 + 100;
77 const int    inf  = 0x3f3f3f3f;
78 const double pi   = acos(-1.0);
79 const double eps  = 1e-8;
80 using namespace std;
81
82 int n, m;
83 int cas, tol, T;
84
85 struct Mat {
86     double mat[5][5];
87     void init() {
88         for(int i=1; i<=2; i++) {
89             for(int j=1; j<=2; j++) {
90                 mat[i][j] = 0.0;
91             }
92         }
93     }
94 };
95 int a[15];
96
97 Mat mmul(Mat A, Mat B) {
98     Mat ans;
99     ans.init();
100     for(int i=1; i<=2; i++) {
101         for(int j=1; j<=2; j++) {
102             for(int k=1; k<=2; k++) {
103                 ans.mat[i][j] += A.mat[i][k] * B.mat[k][j];
104             }
105         }
106     }
107     return ans;
108 }
109
110 Mat mpow(Mat A, int b) {
111     Mat ans;
112     ans.init();
113     for(int i=1; i<=2; i++)
114         ans.mat[i][i] = 1.0;
115     while(b) {
116         if(b & 1)
117             ans = mmul(ans, A);
118         A = mmul(A, A);
119         b >>= 1;
120     }
121     return ans;
122 }
123
124 int main() {
125     double p, q;
126     while(~scanf("%d%lf", &n, &p)) {
127         mes(a, 0);
128         q = 1.0 - p;
129         int flag = 0;
130         for(int i=1; i<=n; i++) {
131             scanf("%d", &a[i]);
132             if(a[i] == 1) {
133                 flag = 1;
134             }
135         }
136         if(flag) {
137             printf("0.0000000\n");
138             continue;
139         }
140         a[n+1] = 0;
141         n++;
142         sort(a+1, a+1+n);
143         double ans = 1.0;
144         Mat A;
145         for(int i=2; i<=n; i++) {
146             if(a[i] == a[i-1])    continue;
147             int tmp = a[i] - a[i-1] + 1;
148             if(tmp == 2) {
149                 ans *= 0.0;
150             } else {
151                 A.mat[1][1] = p;
152                 A.mat[1][2] = q;
153                 A.mat[2][1] = 1.0;
154                 A.mat[2][2] = 0.0;
155                 A = mpow(A, tmp-2);
156 //                for(int i=1; i<=2; i++) {
157 //                    for(int j=1; j<=2; j++) {
158 //                        printf("%f%c", A.mat[i][j], j==2 ? ‘\n‘ : ‘ ‘);
159 //                    }
160 //                }
161                 ans *= (1 - A.mat[1][1]);
162             }
163         }
164         printf("%.7f\n", ans);
165     }
166     return 0;
167 }```

## poj 2151 概率dp

//poj 2151 概率dp 1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "algorithm" 5 using namespace std; 6 double dp[33][33]; 7 int M, T, N; //problem, team, least 8 double p[1010][33]; 9 int mai

## poj 2096 (概率DP)

http://poj.org/problem?id=2096 概率DP: 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 double dp[1003][1003]; 5 int main() 6 { 7 int n,s,i,j; 8 cin>>n>>s; 9 for (i=n;i>=0;i--) 10 { 11 for (j=s;j>=0;j--) 12 { 13

## poj 3071 概率dp

//分析:明显的树形关系,题目描述的是一棵高 n + 1的完全二叉树,则 dp[树层号][team号](规定最底层为 0 层,层数朝节点的方向依次递增),推一下就好了 //稍微需要想一下的是比赛双方的选取,下面给出两种方法 //#1 枚举起点划分team区间 1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "algorithm"

## poj 3744 Scout YYF I(概率dp，矩阵优化)

Scout YYF I Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5020   Accepted: 1355 Description YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties,

## POJ 3744 Scout YYF I 矩阵快速幂

Scout YYF I Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4452   Accepted: 1159 Description YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties,