学步园

【题意】

侦察兵YYF要通过一条布有地雷的路，他从1出发，每次有p的几率前进1格，1-p的几率前进两个，现已知所有地雷的位置，求YYF不踩中地雷的几率

【输入】

多组数据

每组数据第一行n、p

接下来一行n个数字表示地雷的位置

【输出】

YYF不踩中雷的几率

f[i]表示在没有地雷的情况下，走i距离的几率

可得f[i]=f[i-1]*p+f[i-2]*(1-p)

类似斐波那契的一个公式

构造一个矩阵

  p   1

1-p 0

这个矩阵的i次方的(1,1)既是f[i]

然后按雷划分一下阶段即可

program poj3744;
type
  square=array [1..2,1..2] of double;
var
  n,i,j,k:longint;
  ans,p:double;
  mine:array [0..11] of longint;
  sol,root:square;

procedure swap (var a,b:longint);inline;
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure qsort (s,e:longint);
var
  i,j,k:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=mine[(s+e) div 2];
  while i<=j do
    begin
      while mine[i]<k do inc(i);
      while mine[j]>k do dec(j);
      if i>j then break;
      swap(mine[i],mine[j]);
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

function matrixmul (a,b:square):square;
var
  ans:square;
  i,j,k:longint;
begin
  fillchar(ans,sizeof(ans),0);
  for i:=1 to 2 do
    for j:=1 to 2 do
      for k:=1 to 2 do
        ans[i,j]:=ans[i,j]+a[i,k]*b[k,j];
  exit(ans);
end;

function power (m:longint):square;
var
  ans,now:square;
begin
  ans[1,1]:=1;
  ans[1,2]:=0;
  ans[2,1]:=0;
  ans[2,2]:=1;
  now:=root;
  while m<>0 do
    begin
      if m and 1 = 1 then ans:=matrixmul(ans,now);
      m:=m div 2;
      now:=matrixmul(now,now);
    end;
  exit(ans);
end;

begin
  while not seekeof do
    begin
      read(n,p);
      for i:=1 to n do
        read(mine[i]);
      qsort(1,n);
      mine[0]:=0;
      root[1,1]:=p;
      root[1,2]:=1;
      root[2,1]:=1-p;
      root[2,2]:=0;
      ans:=1;
      for i:=1 to n do
        if mine[i-1]+1=mine[i] then
          begin
            ans:=0;
            break;
          end
                               else
          begin
            sol:=power(mine[i]-(mine[i-1]+1));
            ans:=ans*(1-sol[1,1]);
          end;
      writeln(abs(ans):0:7);
    end;
end.