POJ 3744 Scout YYF I （概率dp+矩阵快速幂）

时间：2022-03-15 05:21:35

题意：

一条路上，给出n地雷的位置，人起始位置在1，向前走一步的概率p，走两步的概率1-p，踩到地雷就死了，求安全通过这条路的概率。

分析：

如果不考虑地雷的情况，dp[i]，表示到达i位置的概率，dp[i]=dp[i-1]*p+dp[i-2]*(1-p),要想不踩地雷求出到达地雷位置的概率tmp,1-tmp就是不踩地雷的情况，问题又来了，位置最大是10^9,普通递推超时，想到了用矩阵优化。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

struct Mat{

    double mat[][];

};

int pos[],n;

double p;

Mat mul(Mat a,Mat b){

    Mat tmp;

    for(int i=;i<;++i)

    for(int j=;j<;++j){

        tmp.mat[i][j]=;

        for(int k=;k<;++k)

            tmp.mat[i][j]+=a.mat[i][k]*b.mat[k][j];

    }

    return tmp;

}

Mat pow(Mat a,int n){

    Mat tmp;

    memset(tmp.mat,,sizeof(tmp.mat));

    for(int i=;i<;++i)

        tmp.mat[i][i]=;

    while(n){

        if(n&)tmp=mul(tmp,a);

        a=mul(a,a);

        n>>=;

    }

    return tmp;

}

void solve(){

    Mat init,tmp;

    init.mat[][]=p;

    init.mat[][]=1.0-p;

    init.mat[][]=;

    init.mat[][]=;

    sort(pos,pos+n);

    tmp=pow(init,pos[]-);

    double total=(-tmp.mat[][]);

    for(int i=;i<n;++i){

        if(pos[i]==pos[i-])continue;

        tmp=pow(init,pos[i]-pos[i-]-);

        total*=(-tmp.mat[][]);

    }

    printf("%.7lf\n",total);

}

int main()

{

    while(~scanf("%d%lf",&n,&p)){

        for(int i=;i<n;++i)

        scanf("%d",&pos[i]);

        solve();

    }

return ;

}

相关文章