第一次做矩阵快速幂 先讲下矩阵快速幂的基础 矩阵乘法 --
进行 矩阵A(M * N) B(P * Q) 相乘 满足的条件 -----> N==P 然后 相乘得到 C（M * Q）
矩阵乘法也属于线形代数那快 ---- 虽然我还没学 =-=
但一般 都是满足乘法结合律 和 交换律的
但这里 只满足 结合律 -> （A*B)*C == A*(B*C）
而不满足 交换律 就拿刚刚上面的矩阵 A B来说吧 A * B != B * A 即便就在（M == Q） 但要是矩阵内的元素值很特殊 那就另说了~
当你用到 矩阵快速幂的时候 会有一个 很特殊的矩阵 它的作用很大-- 单位矩阵-主对角线（从左上角->右下角）初始值为1 其余地方 初始值为0
它的作用类似于你进行一系列乘法运算将一个存储的值 初始化为1 和进行一系列加法运算将一个存储的值 初始化为0
进行 矩阵快速幂运算的时候 主要运用到了 二进制 的思想 --- 就是将求的 幂的次数 拆分成2进制数后 然后在为1的位置下 进行相加
15 -- 1111 8 + 4 + 2 + 1
关于这种运用二进制的拆分 我还能想到在 多重背包的时候 我们也会涉及 - > 大大耗子 讲的
这个的拆分 代码 应该是核心模块吧
while( n ) { if( n&1 ) { res = multiply( res , base ); // 这里的这个函数名 multiply 就是乘法的意思 } base = multiply( base , base ); }
然后 就 上题目吧
关于这题 一定要看清题目和反应过来
当时 我很stupid地 纠结在 怎么求fib(n)的最后4位呢？ 读了好几遍题目才发现 它要求我们进行对 10000 求模的 =-=
还有我在想 我们得到的那个 2 X 2的矩阵里 怎么找到fib(n)呢？ 也是long long才发现 它起初给我们的式子中就包含了 fib(n)的位置 分别是[1][0] 与 [0][1]
last 。。 贴 代码
1 #include <iostream> 2 using namespace std; 3 4 const int mod = 10000; 5 const int size = 2; 6 7 struct matrix 8 { 9 int m[size][size]; 10 }result, base; 11 12 matrix multiply( matrix a, matrix b ) 13 { 14 matrix temp; 15 for( int i = 0 ; i<size ; i++ ) 16 { 17 for( int j = 0 ; j<size ; j++ ) 18 { 19 temp.m[i][j] = 0; 20 for( int k = 0 ; k<size ; k++ ) 21 temp.m[i][j] = (temp.m[i][j] + a.m[i][k] * b.m[k][j]) % mod; 22 } 23 } 24 return temp; 25 } 26 27 int fastMod(int n) 28 { 29 base.m[0][0] = base.m[0][1] = base.m[1][0] = 1; 30 base.m[1][1] = 0; 31 for( int i = 0 ; i<size ; i++ ) 32 { 33 for( int j = 0 ; j<size ; j++ ) 34 { 35 if( i==j ) 36 result.m[i][j] = 1; 37 else 38 result.m[i][j] = 0; 39 } 40 } 41 while(n) 42 { 43 if( n&1 ) 44 { 45 result = multiply( result , base ); 46 } 47 base = multiply( base , base ); 48 n>>= 1; 49 } 50 return result.m[1][0]; 51 } 52 53 int main() 54 { 55 int n; 56 while( ~scanf("%d", &n) && n!=-1 ) 57 { 58 printf( "%d ",fastMod(n) ); 59 } 60 return 0; 61 }
学习于: 可笑痴狂 Amazing Y 博客园
你可以在他们那边 学到更多 我这只是 自己用来 温习的 =-=
次饭去了 2点了 饿死了 ~