There is no SSR CSU

There is no SSR

CSU - 1917

题意:抽奖，抽到S的概率是p，抽到SR的概率是1-p，抽m次，连续n次抽到SR的概率是多少。

求问题的反面，没有连续n次抽到SR的概率，即有连续1次、2次、……、n-1次抽到SR的概率，dp求解~

n的范围是100，而m可达1e7，O（nm）会超时!

想到矩阵优化，O（n^3 logm）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 const int maxn=105;
 6 struct Matrix{
 7     int n;
 8     double m[maxn][maxn];
 9 
10     void init(int sz){
11         n=sz;
12         for(int i=0;i<n;i++)
13             for(int j=0;j<n;j++)
14                 m[i][j]=0;
15     }
16     Matrix(int sz){init(sz);}
17     void set_I(){
18         for(int i=0;i<n;i++) m[i][i]=1.0;
19     }
20     Matrix operator* (const Matrix& a){
21         Matrix ans(n);
22         for(int k=0;k<n;k++)
23         for(int i=0;i<n;i++)
24         for(int j=0;j<n;j++){
25             ans.m[i][j]+=m[i][k]*a.m[k][j];
26         }
27         return ans;
28     }
29 };
30 int main(){
31     double p,q;
32     int n,m;
33     while(scanf("%lf%lf%d%d",&p,&q,&n,&m)!=EOF){
34         Matrix base(n),ans(n);
35         for(int i=0;i<n;i++) base.m[0][i]=p*pow(q,i);
36         for(int i=1;i<n;i++) base.m[i][i-1]=1.0;
37 
38         ans.set_I();
39         m=m-n;
40         while(m){
41             if(m&1) ans=ans*base;
42             m>>=1;
43             base=base*base;
44         }
45         double res=0;
46         res+=ans.m[0][0]*(1-pow(q,n));
47         for(int i=1;i<n;i++) res+=ans.m[0][i];
48         printf("%.6lf
",1-res);
49     }
50 
51 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 const int maxn=105;
 6 struct Matrix{
 7     int n;
 8     double m[maxn][maxn];
 9 
10     void init(int sz){
11         n=sz;
12         for(int i=0;i<n;i++)
13             for(int j=0;j<n;j++)
14                 m[i][j]=0;
15     }
16     Matrix(int sz){init(sz);}
17     void set_I(){
18         for(int i=0;i<n;i++) m[i][i]=1.0;
19     }
20     Matrix operator* (const Matrix& a){
21         Matrix ans(n);
22         for(int k=0;k<n;k++)
23         for(int i=0;i<n;i++)
24         for(int j=0;j<n;j++){
25             ans.m[i][j]+=m[i][k]*a.m[k][j];
26         }
27         return ans;
28     }
29 };
30 int main(){
31     double p,q;
32     int n,m;
33     while(scanf("%lf%lf%d%d",&p,&q,&n,&m)!=EOF){
34         Matrix base(n),ans(n);
35         for(int i=0;i<n;i++) base.m[i][0]=p*pow(q,i);
36         for(int i=0;i<n-1;i++) base.m[i][i+1]=1.0;
37 
38         ans.m[0][0]=1-pow(q,n);
39         for(int i=1;i<n;i++) ans.m[0][i]=1;
40 
41         m=m-n;
42         while(m){
43             if(m&1) ans=ans*base;
44             m>>=1;
45             base=base*base;
46         }
47         printf("%.6lf
",1-ans.m[0][0]);
48     }
49 
50 }

View Code