[latexpage]

题意:特工YYF潜入敌方根据地,历经千辛万苦后他站在了一条地雷路的第一格。伴随着音乐和鼓点,他每一步有p的概率往前走一格,(p-1)的概率跳过一格到达第二格。求他生还的概率。地雷少于11个,但位置可能达到108大小。

思路:因为YYF不被某个地雷炸死当且仅当他前一秒站在地雷前,后一秒跳到了地雷后,所以我们可以把地雷两两间的路抽出来,设两个地雷间的路从起点到终点的生还概率为x,那么总生还概率为 ∏pi

对于长度为l的路,令f[i]为从第i个格子走到末端的生还概率,那么$f[i]=f[i+1]×p+f[i+2]×(1-p)$

特殊的,f[l]=1-p(只有跳过后一个格子他才暂时安全)

于是,现在我们需要在很短的时间内求出某种长度的路的生还几率。

注意到,f[i]的递推方式很像斐波那契数列,所以我们可以利用矩阵乘法来求f[i]

\begin{equation} \label{eq:poly}
   \begin{Bmatrix}
f(i) \\
f(i+1)
\end{Bmatrix}=
\begin{Bmatrix}
f(i+1) \\
f(i+2)
\end{Bmatrix}*
\begin{Bmatrix}
p & 1-p \\
1 & 0
\end{Bmatrix}
\end{equation}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MX 12
using namespace std;
double p;
int bom[MX],n;
void input(){
    for(int i=1;i<=n;i++)scanf("%d",&bom[i]);
    sort(bom+1,bom+n+1);
}
void mul(double dist[][3],double a[][3],double b[][3]){
    double now[3][3];
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)now[i][j]=0;
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)now[i][j]+=a[k][j]*b[i][k];
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)dist[i][j]=now[i][j];
}
void quickp(double dist[][3],double src[][3],int t){
    double ans[3][3],now[3][3];
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)now[i][j]=src[i][j];
    ans[1][1]=ans[2][2]=1,ans[2][1]=ans[1][2]=0;
    while(t>=1){
        if(t%2==1)mul(ans,now,ans);
        mul(now,now,now);
        t/=2;
    }
    for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)dist[i][j]=ans[i][j];
}
double work(int len){
    if(len==0)return 0;
    double sc[3][3],f[3][3];
    sc[1][1]=p,sc[1][2]=1-p,sc[2][1]=1,sc[2][2]=0,f[1][1]=1-p,f[1][2]=0,f[2][1]=0,f[2][2]=0;
    quickp(sc,sc,len-1);
    mul(f,f,sc);
    return f[1][1];
}
int main(){
    double ans;
    while(cin>>n>>p,ans=1){
        input();
        for(int i=1;i<=n;i++)if(bom[i]!=bom[i-1])ans*=(work(bom[i]-bom[i-1]-1));
        printf("%.7f\n",ans);
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *