POJ 3744 数学题概率题 矩阵乘幂

转的网上的解题报告http://hi.baidu.com/rpsproblem/blog/item/d2cbe67aa1d8b5fd0bd1875f.html，用于备战校赛

按照题目的意思，我们很容易推出公式：
f[i] = p*f[i-1] + (1-p)*f[i-2];
f[i]表示到达位置i的概率（不是安全到达那些很复杂之类的概率，就只是简单的到达的概率）,p为题目给的概率
由于有的原因，就不能直接算了。
这里我用 x[i]表示第i颗的位置
但如果把整个过程按照来分阶段，起点为x[i－1]+1,终点为x[i]，这样每个阶段就只有终点有了（这就很容易算可达概率了）
所以我们可先算在阶段 i ，从起点x[i－1]+1到x[i]的概率qi,这个概率就表示踩到x[i+1]的概率了，那么1-qi就表示这一阶段安全的概率了（我有点不是很明白的就是它具体跳到哪里去了，不过如果按照这样划分阶段的模型，很容易知道结果是正确的）
所以把每个阶段安全可达的概率乘起来就是总的概率了（1－q1）(1-q2)...(1-qn)

这里需要用矩阵乘法快速幂来加速
观察公式
f[i] = p*f[i-1] + (1-p)*f[i-2];
跟Fibonacci数列很像，可用poj3070的方法来构造

| p 1 |
| 1- p 0 |

然后就可用快速幂加速了!

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const double esp = 1e-15;
struct Matrix{
	double matrix[2][2];
	Matrix operator*(const Matrix & m){//重载运算符*，矩阵乘法
		Matrix ans = {0,0,0,0};
		for (int i = 0;i < 2;i++)
			for (int k =0 ;k < 2 ;k ++)
				if (matrix[i][k]>esp)
					for (int j = 0;j < 2;j++)
					{
						ans.matrix[i][j]+=matrix[i][k]*m.matrix[k][j];
					}
				return ans;
	}
}unit = {1,0,0,1};
Matrix pow(Matrix a,int n){//矩阵求幂
	Matrix p = a,ans = unit;
	while(n){
		if (n&1)
		{
			ans = ans*p;
		}
		p = p*p;
		n>>=1;
	}
	return ans;
}
double p;
double cal(int i,int j){//计算踩雷的概率
	if (j == i)
		return 1;
	if (j - i == 1)
		return p;
	Matrix A={p,1,1-p,0};
	A = pow(A,j-i-1);
	return p*A.matrix[0][0] + A.matrix[1][0];
}
int main(){
	int n,i,x[100]={0};
	while(scanf("%d%lf",&n,&p) != EOF){
		for ( i = 1;i <= n;i++)
			scanf("%d",&x[i]);
		sort(x+1,x+1+n);
		if (x[1]==1)
		{
			printf("%.7lf/n", 0);
			continue;
		}
		double ans = 1;
		for ( i = 1;i <= n;i++)
		{
			ans*=(1-cal(x[i-1]+1,x[i]));
		}
		printf("%.7lf/n",ans);
	}
	return 0;
}