POJ 3744 Scout YYF I 矩陣快速幂+機率dp

題意：

  yyf每次能走一步或二步機率為p和1-p

路上有n個地雷  分布在di位置上

問yyf能安全通過這條路的機率

分析

可以容易的得出 dp【i】=p*dp[i-1]+(1-p)*dp[i-2]

因為路長是1e9推會爆炸考慮利用矩陣快速幂優化

要安全跨過某個地累則一定是在地雷的前一步的地方一次性走兩布

然後把通過所有地雷的機率連乘就是答案

ACcode：

#pragma warning(disable:4786)//使命名長度不受限制
#pragma comment(linker, "/STACK:102400000,102400000")//手工開棧
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d,&x,&y,&z)
#define rdl(x) scanf("%I64d,&x);
#define rds(x) scanf("%s",x)
#define rdc(x) scanf("%c",&x)
#define ll long long int
#define ull unsigned long long
#define maxn 1005
#define mod 1000000007
#define INF 0x3f3f3f3f //int 最大值
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define MT(x,i) memset(x,i,sizeof(x))
#define PI  acos(-1.0)
#define E  exp(1)
#define eps 1e-8
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll mul(ll a,ll b,ll p){ll sum=0;for(;b;a=(a+a)%p,b>>=1)if(b&1)sum=(sum+a)%p;return sum;}
inline void Scan(int &x) {
      char c;while((c=getchar())<'0' || c>'9');x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}
using namespace std;
struct N{
    double mat[2][2];
};
N mul(N a,N b){
    N ret;
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j){
            ret.mat[i][j]=0;
            for(int k=0;k<2;++k)
                ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
        }
    return ret;
}
N pow_M(N a,int n){
    N ret;
    memset(ret.mat,0,sizeof(ret.mat));
    for(int i=0;i<2;++i)ret.mat[i][i]=1;
    N tmp=a;
    while(n){
        if(n&1)ret=mul(ret,tmp);
        tmp=mul(tmp,tmp);
        n>>=1;
    }
    return ret;
}
int a[12];
int main(){
    int n,loop,cnt=1;
    double p1,p2;
    while(~scanf("%d%lf",&n,&p1)){
        p2=1.0-p1;
        for(int i=1;i<=n;++i)scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        N tmp,kkk ;
        tmp.mat[0][0]=p1,tmp.mat[0][1]=p2;
        tmp.mat[1][0]=1,tmp.mat[1][1]=0;

        kkk=pow_M(tmp,a[1]-1);
        double ans=1-kkk.mat[0][0];
        for(int i=2;i<=n;++i){
            if(a[i]==a[i-1]){
                    ans=0;
                    break;
            }
            kkk=pow_M(tmp,a[i]-a[i-1]-1);
            ans*=(1-kkk.mat[0][0]);
        }
        printf("%.7f\n",ans);
    }
    return 0;
}
/*
3 0.7
2 4 9
4 0.1
2 3 5 11
4 0.34
1 8 22 4
4 0.7
4 8 14 22
*/