poj 3744 Scout YYF I

 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 using namespace std;
 6 __int64 t,n,i,j,pos[15],pp;
 7 double k,p;
 8 struct matrix
 9 {
10     double arr[15][15];
11 } p1,p2,p3;
12 matrix add(matrix a,matrix b)//矩阵乘法
13 {
14     matrix tmp;
15     memset(tmp.arr,0,sizeof(tmp.arr));
16     for(i=0; i<2; i++)
17         for(j=0; j<2; j++){
18             for(int k=0; k<2; k++)
19                 tmp.arr[i][j]+=a.arr[i][k]*b.arr[k][j];
20         }
21     return tmp;
22 }
23 
24 matrix fast(matrix a,int n,matrix b)//矩阵快速幂
25 {
26     while(n>=1)
27     {
28         if((n&1)!=0)
29         {
30             b=add(a,b);
31         }
32         a=add(a,a);
33         n/=2;
34     }
35     return b;
36 }
37 void init(){
38         p1.arr[0][0]=0,p1.arr[0][1]=1-p,p1.arr[1][0]=1,p1.arr[1][1]=p;
39         memset(p2.arr,0,sizeof(p2.arr));
40         for(int i=0; i<2; i++)
41                 p2.arr[i][i]=1;
42 }
43 int main()
44 {
45     while(cin>>n>>p)
46     {
47         for(int i=0;i<n;i++) scanf("%d",&pos[i]);
48         sort(pos,pos+n);
49         double ans1=1,ans2;
50         if(pos[0]==1){
51             printf("%.7f\n",0);
52             continue;
53         }
54         if(pos[0]==2)
55             ans2=0;
56         else
57             ans2=p;   
58         //初始化第一个位子概率为1，即ans1=1,第二个位置概率要看第一个地雷的位置pos[0]，如果pos[0]=2,则ans2=0,否则ans2=p;
59         for(int i=0;i<n;i++){
60             int cnt;
61             if(i==0) cnt=pos[0]-2;
62             else cnt=pos[i]-pos[i-1];
63             if(cnt==0) continue;
64             init();
65             p3=fast(p1,cnt,p2);
66             double t1,t2;
67             t1=ans1*p3.arr[0][0]+ans2*p3.arr[1][0];
68             t2=ans1*p3.arr[0][1]+ans2*p3.arr[1][1];
69             ans1=t1,ans2=0;
70         }
71         printf("%.7f\n",ans1*(1-p));
72     }
73 }