HDU 1588 Gauss Fibonacci(矩阵快速幂+二分求等比数列和)

发布时间:2017-1-18 17:58:22 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 1588 Gauss Fibonacci(矩阵快速幂+二分求等比数列和)",主要涉及到HDU 1588 Gauss Fibonacci(矩阵快速幂+二分求等比数列和)方面的内容,对于HDU 1588 Gauss Fibonacci(矩阵快速幂+二分求等比数列和)感兴趣的同学可以参考一下。

题目可以看成求 因为fib可以写成A^x的形式,所以就可以将该式改写成等比数列求和的形式。 首项:A^b 公比:A^k 项数:N 该式写作A^b(I+A^k+(A^k)^2+(A^k)^3+'''+(A^k)^(N-1))(I表示单位矩阵) 然后用二分法进行等比数列求和。 #include <cstdio> using namespace std; typedef long long LL; struct Matrix{ LL m[2][2]; }fp,A; LL M; Matrix Multi(Matrix a,Matrix b){ Matrix c; for(int i=0;i<2;i++) for(int j=0;j<2;j++){ c.m[i][j]=0; for(int k=0;k<2;k++) c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j])%M)%M; } return c; } Matrix Power(Matrix a,LL b){ Matrix r; for(int i=0;i<2;i++) for(int j=0;j<2;j++) r.m[i][j]= (i==j); while(b) { if(b&1) r=Multi(r,a); a=Multi(a,a); b>>=1; } return r; } Matrix add(Matrix a,Matrix b){ Matrix c; for(int i=0;i<2;i++) for(int j=0;j<2;j++) c.m[i][j]=(a.m[i][j]+b.m[i][j])%M; return c; } Matrix Matrixsum(LL k){ if(k==1) return fp; Matrix tmp; tmp=Matrixsum(k/2); if(k&1){ Matrix b=Power(fp,k/2+1); tmp=add(tmp,Multi(b,tmp)); tmp=add(tmp,b); } else { Matrix b=Power(fp,k/2); tmp=add(tmp,Multi(tmp,b)); } return tmp; } int main() { LL k,b,n; A.m[0][0]=A.m[0][1]=A.m[1][0]=1;A.m[1][1]=0; while(~scanf("%I64d%I64d%I64d%I64d",&k,&b,&n,&M)){ Matrix con=Power(A,b); fp=Power(A,k); Matrix pp=Matrixsum(n-1); pp.m[0][0]+=1;pp.m[1][1]+=1; pp=Multi(pp,con); printf("%I64d\n",pp.m[0][1]%M); } return 0; }

上一篇:00-iOS开发经典语录
下一篇:java Math.round()

相关文章

相关评论