51nod 1836:战忽局的手段
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1836
矩阵快速幂
从题目所给的数据范围来看复杂度应该为O(1)或者O(lgn),于是定义ƒ(x)为n个事件,x次忽悠下的期望事件数
很明显可以得到这样一个递推式:ƒ(x)=ƒ(x-1)+[1-ƒ(x-1)/n]=1+(1-1/n)ƒ(x-1)
于是我们就可以构造矩阵以O(lgn)的复杂度来解这道题啦。
/*注意这道题卡精度,可以用__float128来保存中间变量减少精度丢失*/
代码如下:
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 typedef long long ll; 5 ll T,n,m; 6 struct matrix{ 7 __float128 mp[2][2]; 8 friend matrix operator * (matrix a,matrix b){ 9 matrix t; 10 for(int i=0;i<2;++i) 11 for(int j=0;j<2;++j){ 12 t.mp[i][j]=0; 13 for(int k=0;k<2;++k) 14 t.mp[i][j]+=a.mp[i][k]*b.mp[k][j]; 15 } 16 return t; 17 } 18 }E,A; 19 matrix pow(matrix A,ll n){ 20 matrix base=A,ans=E; 21 while(n){ 22 if(n&1)ans=ans*base; 23 base=base*base; 24 n>>=1; 25 } 26 return ans; 27 } 28 int main(void){ 29 E.mp[0][0]=E.mp[1][1]=1; 30 E.mp[0][1]=E.mp[1][0]=0; 31 scanf("%lld",&T); 32 while(T--){ 33 scanf("%lld%lld",&n,&m); 34 A.mp[0][0]=(__float128)1-(__float128)1/(__float128)n;A.mp[0][1]=1; 35 A.mp[1][0]=0;A.mp[1][1]=1; 36 matrix temp=pow(A,m-1); 37 double ans=(double)(temp.mp[0][0]+temp.mp[0][1]); 38 printf("%.7lf ",ans); 39 } 40 }
当然也可以将递推式继续推算下去,以O(1)的复杂度解决。(数据小的话直接用math.h,否则直接取极限)