POJ-3744-概率dp+矩阵幂(分段)
Time Limit:1000MS | Memory Limit:65536K | |
Total Submissions:10214 | Accepted:2980 |
Description
Input
Output
Sample Input
1 0.5
2
2 0.5
2 4
Sample Output
0.5000000
0.2500000
Source
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #include<cstdio> 5 #include<stack> 6 #include<set> 7 #include<map> 8 #include<cmath> 9 #include<ctime> 10 #include<time.h> 11 #include<algorithm> 12 using namespace std; 13 #define mp make_pair 14 #define pb push_back 15 #define debug puts("debug") 16 #define LL long long 17 #define pii pair<int,int> 18 #define eps 1e-12 19 20 struct matrix{ 21 double a[2][2]; 22 matrix& operator*(matrix &tmp){ 23 matrix ans; 24 memset(ans.a,0,sizeof(ans.a)); 25 for(int i=0;i<2;++i){ 26 for(int j=0;j<2;++j){ 27 for(int k=0;k<2;++k){ 28 ans.a[i][j]+=a[i][k]*tmp.a[k][j]; 29 } 30 } 31 } 32 return ans; 33 } 34 }A,E; 35 double qpow(matrix H,int b){ 36 matrix ans=E; 37 while(b){ 38 if(b&1) ans=ans*H; 39 H=H*H; 40 b>>=1; 41 } 42 return ans.a[0][0]; 43 } 44 int main() 45 { 46 int n,m,i,j,k,t; 47 int x[15]; 48 double P; 49 E.a[0][0]=E.a[1][1]=1; 50 E.a[0][1]=E.a[1][0]=0; 51 while(scanf("%d%lf",&n,&P)!=EOF){ 52 A.a[0][0]=P; 53 A.a[1][0]=1.00-P; 54 A.a[0][1]=1; 55 A.a[1][1]=0; 56 for(i=1;i<=n;++i) scanf("%d",x+i); 57 sort(x+1,x+1+n); 58 bool ok=1; 59 for(i=2;i<=n;++i) 60 if(x[i]-x[i-1]==1) ok=0; 61 if(ok==0||x[1]==1){ 62 printf("%.7f\n",0.0); 63 continue; 64 } 65 double ans=1; 66 ans=ans*(1-P)*qpow(A,x[1]-2); 67 for(i=2;i<=n;++i){ 68 if(x[i]==x[i-1]) continue; 69 ans=ans*((double)1-P)*qpow(A,x[i]-x[i-1]-2); 70 } 71 printf("%.7f\n",ans); 72 } 73 return 0; 74 }