题意:YYF要深入敌后,现在要经过一条地雷路,这些路上有很多的地雷(这些地雷都是长在地图上的,看得到,不用怕)。然后YYF有p的概率走一步,有1-p的概率跳两步。现在问你他安全走过雷区的概率是多少?


自己先在草稿纸上画画就能推出递推式,比如我是这样画的:

x o

x _ o

x _ _ o

。。。。。。

(注意,题目给的数据必定无序,所以先排序)

x代表安全起点,o代表地雷,然后手动模拟概率就可以得出递推式:

dp[i]=dp[i-1]*p+dp[i-2]*(1-p);

然后发现GG,i最大达到了100000000,显然TLE。怎么办?

有两种方法解决,我们先说简单的(后面第二种比较有趣,别只顾着简单啊喂):

因为安全走下一步的概率总是不断地进行乘积,所以在题目给定的精度下最终肯定会趋于一个一个定值,所以我们只需要先打个表,然后大于这个表的都按最后一个数的概率来算即可。


代码:

StatusAccepted
Memory184kB
Length728
LangC++
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40;
double p, dp[maxn], ans;
int n, res[maxn];
int main()
{
    res[0]=0;
    while(~scanf("%d %lf", &n, &p)){
        for(int i=1;i<=n;i++){
            scanf("%d", &res[i]);
        }
        sort(res+1, res+n+1);
        dp[0]=1-p;dp[1]=p*(1-p);
        for(int i=2;i<maxn;i++){
            dp[i]=dp[i-1]*p+dp[i-2]*(1-p);
        }
        ans=1;
        for(int i=1;i<=n;i++){
            if(res[i]-res[i-1]==1){
                ans=0;break;
            }
            int g=res[i]-res[i-1]-2;
            if(g>=maxn)ans*=dp[maxn-1];
            else ans*=dp[g];
        }
        printf("%.7lf\n", ans);
    }
    return 0;
}


好,下面是比较正规的做法,重头戏:

利用线性代数里面的矩阵来做!EXM?这怎么和矩阵扯一块了?好吧,你必须得承认线代就是这么的神奇。前几天才看过矩阵快速幂没写过练习代码,这次刚好有个题,于是,,,再次看题解用矩阵做了一遍。

呐,递推式我们已经在上面给出了。为了引题,我们先来扯扯斐波拉契数列的矩阵快速求法。

我们知道,线性代数里面乘积是这样的:

blob.png

再看斐波拉契递推式:

F(i)=F(i-1)+F(i-2)

我们构造一个向量矩阵:

blob.png

进而可以推导A矩阵如2所示。

然后就可以推导第i项的斐波拉契是多少了,如下图所示。根据不同的起始项取结果矩阵的不同位置,刚好有人问了A(i-1)怎么提取出来的,我就顺便提示一下,乘以一个A可以跳一步,乘以i-1个A就可以 跳i-1步刚好可以到达i的位置。

blob.png

好,下面是我们这个题的递推式,再拿出来:

dp[i]=dp[i-1]*p+dp[i-2]*(1-p);

和斐波拉契数列很像吧?自己按照上面的方法推导一下,就可以得出A矩阵为:

|p 1-p |

|1    0  |


我们假定现在他前面一个就是炸弹,那么他现在只有1步可以走,所以他必须跳过去,概率为1-p,所以有dp[0]=0, dp[1]=1-p。

假设现在他距离无限远在x+1处,炸弹在y处,那么x处有一个炸弹(假定0处是炸弹),他走到y-1处还剩下一步可以走,那么从y-1往后退x-y-2步到达x+1安全位置(不好理解看下面的图),所以:

dp[1]   * A^(y-x-2) = dp[n]

dp[0]                          dp[n-1]


_炸弹______YYF_______________________________YYF____炸弹________________________________

    x            x+1                                            y-1     y

所以我们只需要遍历所有的炸弹乘起来就好。(注意思考必定被炸死的情况哦!)


代码:

StatusAccepted
Memory184kB
Length1235
LangC++
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=15;
const int maxm=2;
int n, res[maxn], l, r;
double p, ans;
struct Matrix{
    double ret[maxm][maxm];
};
Matrix I={1, 0, 0, 1};
Matrix A={p, 1-p, 1, 0};
Matrix operator*(Matrix a, Matrix b){
    Matrix c;
    for(int i=0;i<maxm;i++){
        for(int j=0;j<maxm;j++){
            double tmp=0;
            for(int k=0;k<maxm;k++){
                tmp+=a.ret[i][k]*b.ret[k][j];
            }
            c.ret[i][j]=tmp;
        }
    }
    return c;
}
Matrix operator^(Matrix c, int n){
    Matrix ans=I, a=c;
    while(n){
        if(n%2)ans=ans*a;
        n/=2;
        a=a*a;
    }
    return ans;
}
int main()
{
    res[0]=0;
    while(~scanf("%d %lf", &n, &p)){
        for(int i=1;i<=n;i++){
            scanf("%d", &res[i]);
        }
        sort(res, res+n);
        ans=1;l=0;
        A.ret[0][0]=p;A.ret[0][1]=1-p;
        A.ret[1][0]=1;A.ret[1][1]=0;
        for(int i=1;i<=n;i++){
            if(res[i]-res[i-1]==1){ans=0;break;}
            int len=res[i]-res[i-1]-2;
            Matrix tmp=A^len;
            ans*=(tmp.ret[0][0]*(1-p));
        }
        printf("%.7lf\n", ans);
    }
    return 0;
}