<h1 id="heading">题目</h1>
{% fold 点击显/隐题目 %}
<div class="oj"><div class="part" title="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.
</div><div class="part" title="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].
</div><div class="part" title="Output">
For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
1 0.5
2
2 0.5
2 4
</div><div class="output part" title="Sample Output">
0.5000000
0.2500000
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
不考虑地雷的情况下,可以很容易得到递推式: 
<code>dp(i) = p*dp(i-1)+(1-p)*dp(i-2)</code>
然而由于距离可以达到<code>100000000</code>,直接去计算需要非常多的内存
根据概率的知识,可以知道,能够通过每一个雷区的概率等于1-踩雷的概率 
而通过整个区域的概率就是通过每个雷区的概率的乘积
根据雷区的位置,可以把整个区域分成多段,每一段有且仅有一个地雷 
计算每一段的概率即可
不过每一段的长度也有可能是非常长的,要解决它有两种思路: 
高中数学优化和高等数学优化
对于 {% raw %}<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>a</mi><mi>n</mi></msub><mo>=</mo><mi>p</mi><mo>×</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>p</mi><mo stretchy="false">)</mo><mo>×</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>−</mo><mn>2</mn></mrow></msub></mrow><annotation encoding="application/x-tex">a_n = p \times a_{n-1}+(1-p) \times a_{n-2}</annotation></semantics></math>an​=p×an−1​+(1−p)×an−2​{% endraw %} ,求其通项公式 
化简步骤如下:
{% raw %} 

\begin{align*}
a_n &amp;= p \times a_{n-1} + (1-p) \times a_{n-2} \\
a_n &amp;= (1-(1-p)) \times a_{n-1} + (1-p) \times a_{n-2} \\
a_n &amp;= a_{n-1} - (1-p) \times a_{n-1} + (1-p) \times a_{n-2} \\
a_n - a_{n-1} &amp;= -(1-p) (a_{n-1} - a_{n-2}) \\
\end{align*}
 
{% endraw %}
这时,已经可以看出等号两边的结构相等了 
设一个辅助数列 
{% raw %} 
$$ 
\begin{align*} 
令 b_n &amp;= a_{n+1}-a_{n} \ 
\ 
有 b_n &amp;= (p-1) \times b_{n-1} \ 
可得 b_n &amp;= b_1 \times (p-1)^n-1 \ 
b_{n-1} &amp;= b_1 \times (p-1)^{n-2} \ 
b_{n-1} &amp;= a_{n} - a_{n-1}\ 
\ 
a_{n} - a_{n-1} &amp;= (a_2 - a_1) \times (p-1)^{n-2} \ 
a_{n-1} - a_{n-2} &amp;= (a_2 - a_1) \times (p-1)^{n-3} \ 
&amp; ...\ 
a_{2} - a_{1} &amp;= (a_2 - a_1) \times (p-1)^{0} \ 
\ 
a_{n} - a_{1} &amp;= \sum_{i=0}^{n-2} ((a_2 - a_1) \times (p-1)^i) \ 
a_{n} - a_{1} &amp;= (a_2 - a_1) \times \sum_{i=0}^{n-2} (p-1)^i) \ 
a_{n} - a_{1} &amp;= (a_2 - a_1) \times \frac {1 \times (1-(p-1)^{n-1})} {1-(p-1)} \ 
a_{n} &amp;= a_{1} + (a_2 - a_1) \times \frac {1-(p-1)^{n-1}} {2-p} \
\ 
其中 a_1 &amp;= 1 , a_2 = p\ 
a_{n} &amp;= 1 + (p-1) \times \frac {1-(p-1)^{n-1}} {2-p} \
\end{align*} 
$$ 
{% endraw %}
也即,我们有了dp的通项公式 
<code>dp[i] = 1 + (p-1)*(1-(p-1)^(n-1)/(2-p))</code>
平方部分使用快速幂计算即可
当然,也可以使用高等数学部分的矩阵乘法
<h1 id="endpmatrix">{% raw %}$ 
\begin{pmatrix} 
p &amp; 1-p\ 
1 &amp; 0 
\end{pmatrix} 
\times 
\begin{pmatrix} 
dp[i] \ 
dp[i-1] 
\end{pmatrix}</h1>
<h1 id="endpmatrix-1">\begin{pmatrix} 
p \times dp[i] + (1-p) \times dp[i-1] \ 
dp[i] 
\end{pmatrix}</h1>
\begin{pmatrix} 
dp[i+1] \ 
dp[i] 
\end{pmatrix} 
${% endraw %}
<h1 id="endpmatrix-2">那么可以推出dp[i]的表达式为 
{% raw %}$ 
\begin{pmatrix} 
dp[i]\ 
dp[i-1] 
\end{pmatrix}</h1>
\begin{pmatrix} 
p &amp; 1-p\ 
1 &amp; 0 
\end{pmatrix} ^ {n-2} 
\times 
\begin{pmatrix} 
p\ 
1 
\end{pmatrix} 
${% endraw %}
使用快速矩阵幂计算即可,需要注意两个雷紧挨着的时候的情况
<h1 id="heading-2">代码</h1>
{% fold 点击显/隐递推方法代码 %}```cpp Scout YYF递推 <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份 
// 
#define debug 
#include <ctime> 
/// 
#include <algorithm> 
#include <cstdio> 
#include <cstring> 
#include <iomanip> 
#include <iostream> 
#include <set> 
using namespace std;
const int maxn = 15;
double pow(double a, int n) { 
if (n == 0) 
return 1.0; 
if (n == 1) 
return a; 
double ans = pow(a, n / 2); 
ans = ans * ans; 
if (n &amp; 1) 
ans *= a; 
return ans; 
} 
double f(int n,double p){ 
return 1 + (p - 1) * (1 - pow(p - 1, n - 1)) / (2 - p); 
}
int mines[maxn];
int main() { 
#ifdef debug 
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin); 
int START = clock(); 
#endif 
cin.tie(0); 
cin.sync_with_stdio(false); 
int n; 
double p; 
while (cin &gt;&gt; n &gt;&gt; p) { 
mines[0] = 0; 
for (int i = 1; i &lt;= n; i++) 
cin &gt;&gt; mines[i];
<pre><code> sort(mines + 1, mines + 1 + n);

 double ans = 1;
 for (int i = 1; i &lt;= n; i++) {
 int dis = mines[i] - mines[i - 1];

 double dp = f(dis,p); 
 //cout &lt;&lt;&quot;\t &quot;&lt;&lt;dis&lt;&lt;&quot; &quot;&lt;&lt; dp&lt;&lt;endl;
 ans *= (1 - dp);
 }

 cout &lt;&lt; fixed &lt;&lt; setprecision(7) &lt;&lt; ans &lt;&lt; endl;
}
</code></pre>
#ifdef debug 
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC); 
#endif 
return 0; 
}
<pre style="background-color:#fff">{% endfold %}

{% fold 点击显/隐矩阵方法代码 %}```cpp Scout YYF矩阵 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include &lt;ctime&gt;
//*/
#include &lt;algorithm&gt;
#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;iomanip&gt;
#include &lt;iostream&gt;
#include &lt;set&gt;
using namespace std;

const int maxn = 15;

class Matrix {
 public:
 static const int LINE = 2; //行列数
 double matrix[LINE][LINE];

 Matrix() {
 for (int i = 0; i &lt; LINE; i++)
 for (int j = 0; j &lt; LINE; j++)
 matrix[i][j] = 0;
 }

 Matrix operator*(Matrix rhs) { return mul(*this, rhs); }
 Matrix operator^(int n) { return pow(*this, n); }

 static Matrix mul(Matrix a, Matrix b) {
 Matrix ans;
 for (int i = 0; i &lt; LINE; i++)
 for (int j = 0; j &lt; LINE; j++) {
 ans.matrix[i][j] = 0;
 for (int k = 0; k &lt; LINE; k++)
 ans.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j];
 }
 return ans;
 }

 static Matrix pow(Matrix a, int n) {
 if (n == 0) {
 Matrix E;
 for (int i = 0; i &lt; LINE; i++)
 E.matrix[i][i] = 1;
 return E;
 }
 if (n == 1)
 return a;
 Matrix ans = pow(a, n / 2);
 ans = ans * ans;
 if (n &amp; 1)
 return ans * a;
 return ans;
 }
 void print() {
 for (int i = 0; i &lt; LINE; i++) {
 printf(&#34;|&#34;);
 for (int j = 0; j &lt; LINE; j++)
 printf(&#34;%f &#34;, matrix[i][j]);
 printf(&#34;|\n&#34;);
 }
 printf(&#34;\n&#34;);
 }
};

int mines[maxn];

int main() {
#ifdef debug
 freopen(&#34;in.txt&#34;, &#34;r&#34;, stdin);
 int START = clock();
#endif
 cin.tie(0);
 cin.sync_with_stdio(false);

 int n;
 double p;
 while (cin &gt;&gt; n &gt;&gt; p) {
 mines[0] = 0;
 for (int i = 1; i &lt;= n; i++)
 cin &gt;&gt; mines[i];

 sort(mines + 1, mines + 1 + n);

 double ans = 1;
 for (int i = 1; i &lt;= n; i++) {
 int dis = mines[i] - mines[i - 1];

 if (dis == 1) {
 ans = 0;
 break;
 }

 Matrix dp, pro;
 dp.matrix[0][0] = p;
 dp.matrix[1][0] = 1;

 pro.matrix[0][0] = p;
 pro.matrix[0][1] = 1 - p;
 pro.matrix[1][0] = 1;

 dp = Matrix::pow(pro, dis - 2) * dp;

 dp.print();

 ans *= (1 - dp.matrix[0][0]);
 }

 cout &lt;&lt; fixed &lt;&lt; setprecision(7) &lt;&lt; ans &lt;&lt; endl;
 }

#ifdef debug
 printf(&#34;Time:%.3fs.\n&#34;, double(clock() - START) / CLOCKS_PER_SEC);
#endif
 return 0;
}
</pre>{% endfold %}

POJ 3744.Scout YYF