首页 > 代码库 > 矩阵快速幂---BestCoder Round#8 1002
矩阵快速幂---BestCoder Round#8 1002
当要求递推数列的第n项且n很大时，怎么快速求得第n项呢?
可以用矩阵快速幂来加速计算。
我们可以用矩阵来表示数列递推公式
比如fibonacci数列 可以表示为 [f(n) f(n-1)] = [f(n-1) f(n-2)] [ 1 1 ]
[ 1 0 ]
设A = [ 1 1 ]
[ 1 0 ]
[f(n) f(n-1)] = [f(n-2) f(n-3)]*A*A
[f(n) f(n-1)] = [f(2) f(1)]*A^(n-2)
矩阵满足结合律，所以先计算A^(n-2)，这个可以用一般快速二分幂的思想来计算。
BestCoder Round#8 1002
当n为奇数时，f(n) = 2 * f(n-1) + 1
当n为偶数时，f(n) = 2 * f(n-1)
将偶数项独立出来形成单独的一个数列 b(2*n) = 2 * b(2*n-1) + 1 = 4 * (2*n-2) + 2
即b(n) = 4 * b(n-1) + 2
当n为偶数时，计算b(n/2)即可
当n为奇数时，计算b(n/2) * 2 + 1即可
因为n很大，可以用矩阵快速幂来加速
递推矩阵为 [b(n) 2] = [b(n-1] 2] * [ 4 0 ]
[ 1 1 ]
1 #include <stdio.h> 2 #include <string.h> 3 typedef long long LL; 4 struct Matrix 5 { 6 LL matrix[2][2]; 7 }; 8 int n,m; 9 Matrix operator *(const Matrix &lhs, const Matrix &rhs)10 {11 Matrix res;12 memset(res.matrix, 0 ,sizeof(res.matrix));13 int i,j,k;14 for(k=0; k<2; ++k)15 for(i=0; i<2; ++i)16 {17 if(lhs.matrix[i][k] == 0) continue;18 for(j=0; j<2; ++j)19 {20 if(rhs.matrix[k][j] == 0) continue;21 res.matrix[i][j] = (res.matrix[i][j] + lhs.matrix[i][k] * rhs.matrix[k][j]) % m;22 }23 }24 return res;25 }26 Matrix operator ^(Matrix a, int k)27 {28 Matrix res;29 int i,j;30 for(i=0; i<2; ++i)31 for(j=0; j<2; ++j)32 res.matrix[i][j] = (i == j);33 while(k)34 {35 if(k & 1)36 res = res * a;37 a = a * a;38 k>>=1;39 }40 return res;41 }42 43 int main()44 {45 while(scanf("%d%d",&n,&m)!=EOF)46 {47 Matrix a;48 a.matrix[0][0] = 4;49 a.matrix[0][1] = 0;50 a.matrix[1][0] = a.matrix[1][1] = 1;51 int k = n / 2;52 a = a ^ k;53 LL ans =(2 * a.matrix[1][0]) % m;54 if(n & 1 == 1)55 ans = (ans * 2 + 1) % m;56 printf("%lld\n",ans);57 58 59 }60 return 0;61 }
矩阵快速幂---BestCoder Round#8 1002
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。