算法竞赛进阶指南，156页，矩阵乘法
本题要点： 1、 n <= 2 * 10^9, 如果使用迭代法计算 斐波那契数列，显然会超时。 2、 题目给出了提示， 2 * 2 阶矩阵（假设叫特殊矩阵） 的n次方，得到的矩阵，就是 fib[n], fib[n - 1], f[n - 1], f[n - 2] 当然计算矩阵的n次方，不能一个一个的成，那样时间复杂度也是 O(n). 应该使用二进制的方法，扫描 n 值得二进制的每一位，看看是不是1， 用矩阵B 来存放 特殊矩阵 的 2， 4， 8， 16 次方，… 类似于快速幂中的二进制优化。 3、 这里使用了一维数组来模拟矩阵的乘法，写得很土。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; long long n, mod; int A[5], B[5]; void multi(int a[], int b[]) { int c[5]; c[1] = (a[1] * b[1] + a[2] * b[3]) % mod; c[2] = (a[1] * b[2] + a[2] * b[4]) % mod; c[3] = (a[3] * b[1] + a[4] * b[3]) % mod; c[4] = (a[3] * b[2] + a[4] * b[4]) % mod; for(int i = 1; i <= 4; ++i) { a[i] = c[i]; } } void solve() { A[1] = 0, A[2] = 1, A[3] = 1, A[4] = 0; B[1] = B[2] = B[3] = 1, B[4] = 0; long long b = n; while(b) { if(b & 1) { multi(A, B); } multi(B, B); b >>= 1; } printf("%d\n", A[1]); } int main() { mod = 10000; while(scanf("%lld", &n) != EOF && n != -1) { solve(); } return 0; } /* 0 9 999999999 1000000000 -1 */ /* 0 34 626 6875 */