POJ-3744 Scout YYF I

Description

题意大概是这样的，你要走一段路，这段路犹如一长串格子，你最开始在1号格子上。每次你有p的概率走一个格子，1-p的概率走两个格子。并且这一长串格子中最多有10个地雷，当走到有地雷的格子上你就挂了。问你能活下来的概率是多少。地雷在的格子编号<=10^8，0<p<1;

我们先考虑走到i号格子的概率p[i]，假设没有地雷，

p[i]=p*p[i-1]+(1-p)*p[i-2].如果有地雷，那么这个格子上走来的概率就是0。所以我们对每两个地类之间矩阵乘法加速DP，到了下一个地雷，将该位置上的概率变成0；走到最后一个地雷后面的格子的概率就是答案了（考虑，为什么不是p[a[n]+1]+p[a[n]+2]）。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
double p;int n;
int a[20];
struct node2
{
	double p[2][2];
	node2(double x){p[0][0]=x;p[0][1]=1.0;p[1][0]=1.0-x;p[1][1]=0;}
	node2(){p[0][0]=p[1][0]=p[0][1]=p[1][1]=0.0;}
	node2 operator * (node2 x)
	{
		node2 ret;
		for(int i=0;i<=1;i++)
			for(int j=0;j<=1;j++)
				for(int k=0;k<=1;k++)
					ret.p[i][j]+=p[i][k]*x.p[k][j];
		return ret;
	}
	void output()
	{
		printf("%.2lf %.2lf\n",p[0][0],p[0][1]);
		printf("%.2lf %.2lf\n",p[1][0],p[1][1]);
	}
};


struct node1
{
	double p[2];
	node1(double x,double y) {p[0]=x;p[1]=y;}
	node1(){p[0]=p[1]=0.0;}
	node1 operator * (node2 x)
	{
		node1 ret;
		for(int i=0;i<=1;i++)
			for(int j=0;j<=1;j++)
				ret.p[i]+=p[j]*x.p[j][i];
		return ret;
	}
	void output()
	{
		printf("%.2lf %.2lf\n",p[0],p[1]);
	}
};

node1 pow(node1 x,int y)
{
	node2 z=node2(p);
	while(y)
	{
		if(y&1) x=x*z;
		z=z*z; y>>=1;
	}
	return x;
}
int main()
{
	while(scanf("%d%lf",&n,&p)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		if(a[1]==1)
		{
			printf("0.0000000\n");
			continue;
		} 
		node1 tmp=node1(1.0,0.0);
		int now=1;
		for(int i=1;i<=n;i++)
		{
			tmp=pow(tmp,a[i]-now-1);
			tmp.p[1]=tmp.p[0];tmp.p[0]=0.0;
			now=a[i];
		}
		node2 y=node2(p);
		tmp=tmp*y;
		printf("%.7lf\n",tmp.p[0]);
	}
	return 0;
}