poj 3744 概率dp+矩阵快速幂

时间：2023-12-03 08:18:38
题意：在一条布满地雷的路上，你现在的起点在1处。在N个点处布有地雷，1<=N<=10。地雷点的坐标范围：[1,100000000].
每次前进p的概率前进一步，1-p的概率前进1-p步。问顺利通过这条路的概率。就是不要走到有地雷的地方。
链接：点我
设dp[i]表示到达i点的概率，则 初始值 dp[1]=1.
很容易想到转移方程： dp[i]=p*dp[i-1]+(1-p)*dp[i-2];
但是由于坐标的范围很大，直接这样求是不行的，而且当中的某些点还存在地雷。
N个有地雷的点的坐标为 x[1],x[2],x[3]```````x[N].
我们把道路分成N段：
1~x[1];
x[1]+1~x[2];
x[2]+1~x[3];
`
x[N-1]+1~x[N].
转移矩阵：
  dp[i]    | p ,1-p  |    dp[i-1]
            =|            |*
dp[i-1]   | 1 , 0    |   dp[i-2]
这样每一段只有一个地雷。我们只要求得通过每一段的概率。乘法原理相乘就是答案。
对于每一段，通过该段的概率等于1-踩到该段终点的地雷的概率。
就比如第一段 1~x[1].  通过该段其实就相当于是到达x[1]+1点。那么p[x[1]+1]=1-p[x[1]].
但是这个前提是p[1]=1,即起点的概率等于1.对于后面的段我们也是一样的假设，这样就乘起来就是答案了。
对于每一段的概率的求法可以通过矩阵乘法快速求出来。
 #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);

     }

 }

相关文章