dp[i] | p ,1-p | dp[i-1]
=| |*
dp[i-1] | 1 , 0 | dp[i-2]
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt,x[MAXN],dp[MAXN];
struct Matrix
{
double mat[][];
};
Matrix mul(Matrix a,Matrix b)
{
Matrix ret;
for(int i=;i<;i++)
for(int j=;j<;j++)
{
ret.mat[i][j]=;
for(int k=;k<;k++)
ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
}
return ret;
}
Matrix pow_M(Matrix a,int n)
{
Matrix ret;
memset(ret.mat,,sizeof(ret.mat));
for(int i=;i<;i++)ret.mat[i][i]=;
Matrix temp=a;
while(n)
{
if(n&)ret=mul(ret,temp);
temp=mul(temp,temp);
n>>=;
}
return ret;
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
double p;
while(scanf("%d%lf",&n,&p)!=EOF)
{
double ans=;
for(i=;i<n;i++) scanf("%d",x+i);
sort(x,x+n);
Matrix a,b;
a.mat[][]=p;
a.mat[][]=-p;
a.mat[][]=;
a.mat[][]=;
b=pow_M(a,x[]-);
ans*=(-b.mat[][]);
for(i=;i<n;i++)
{
if(x[i]==x[i-]) continue;
b=pow_M(a,x[i]-x[i-]-);
ans*=(-b.mat[][]);
}
printf("%.7f\n",ans);
}
}
poj 3744 概率dp+矩阵快速幂的更多相关文章
-
Scout YYF I POJ - 3744(概率dp + 矩阵快速幂)
题意: 一条路上有n个地雷,你从1开始走,单位时间内有p的概率走一步,1-p的概率走两步,问安全通过这条路的概率 解析: 很容易想到 dp[i] = p * dp[i-1] + (1 - p) * d ...
-
POJ 3744 Scout YYF I 概率dp+矩阵快速幂
题目链接: http://poj.org/problem?id=3744 Scout YYF I Time Limit: 1000MSMemory Limit: 65536K 问题描述 YYF is ...
-
poj3744 (概率DP+矩阵快速幂)
http://poj.org/problem?id=3744 题意:在一条铺满地雷的路上,你现在的起点在1处.在N个点处布有地雷,1<=N<=10.地雷点的坐标范围:[1,10000000 ...
-
poj4474 Scout YYF I(概率dp+矩阵快速幂)
Scout YYF I Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4100 Accepted: 1051 Descr ...
-
POJ3744 Scout YYF I 概率DP+矩阵快速幂
http://poj.org/problem?id=3744 题意:一条路,起点为1,有概率p走一步,概率1-p跳过一格(不走中间格的走两步),有n个点不能走,问到达终点(即最后一个坏点后)不踩坏点的 ...
-
POJ 3744 Scout YYF I (概率dp+矩阵快速幂)
题意: 一条路上,给出n地雷的位置,人起始位置在1,向前走一步的概率p,走两步的概率1-p,踩到地雷就死了,求安全通过这条路的概率. 分析: 如果不考虑地雷的情况,dp[i],表示到达i位置的概率,d ...
-
poj 3744 Scout YYF 1 (概率DP+矩阵快速幂)
F - Scout YYF I Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Sub ...
-
bnuoj 34985 Elegant String DP+矩阵快速幂
题目链接:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=34985 We define a kind of strings as elegant s ...
-
poj 3070 &;&; nyoj 148 矩阵快速幂
poj 3070 && nyoj 148 矩阵快速幂 题目链接 poj: http://poj.org/problem?id=3070 nyoj: http://acm.nyist.n ...
随机推荐
-
.NET面试题系列[11] - IEnumerable<;T>;的派生类
“你每次都选择合适的数据结构了吗?” - Jeffery Zhao .NET面试题系列目录 ICollection<T>继承IEnumerable<T>.在其基础上,增加了Ad ...
-
jQuery源代码阅读之二——jQuery静态属性和方法
一.jQuery.extend/jQuery.fn.extend //可接受的参数类型如下:jQuery.extend([deep],target,object1,[objectN]) jQuery. ...
-
Linux 进程退出后自动启动
/********************************************************************** * Linux 进程退出后自动启动 * 说明: * 在系 ...
-
如何在android的mk文件添加依赖已经编译好的库
用$(MY_LIB)是代表你的库的所在目录,目录结构是这样 MY_LIB |---include |-----xxx.h |-----xxx.h |---lib |----MYLIB.a LOCAL_ ...
-
java遍历Map的几种方式
1.遍历map的几种方式:private Hashtable<String, String> emails = new Hashtable<String, String>(); ...
-
FindWindow()&;&;FindWindowEx
这个函数呢,我一般用来自动刷刷网页啥的比如我最近就在刷52破解的在线时间,好啦怎么用是你自己的事情. FindWindow()主要用来获取目标句柄 或着说窗口的权限 HWND FindWindow( ...
-
Linux下快速比较两个目录的不同
曾多次想要在Linux下比较目录a和目录b中文件列表的差别,然后对目录a比目录b中多出的文件.少掉的文件分别做处理.但是,在网上搜索了多次也都没找到能直接处理好的工具. 所以想了很多不少方法,自我感觉 ...
-
CentOS,crontab的学习、使用、问题解决记录
参考:http://blog.csdn.net/luanwpp/article/details/7490871 参考: http://mp.weixin.qq.com/s?src=11&tim ...
-
有哪些知名的公司在用Python
谷歌:Google App Engine.code.Google.com.Google earth.谷歌爬虫.Google广告等项目都在大量使用Python开发 CIA:美国中情局网站就是用Pytho ...
-
Javascript 异步处理与计时跳转
实现计时跳转的代码: <html lang="en"> <head> <meta charset="UTF-8"> < ...