POJ 3070 Fibonacci （算法竞赛进阶指南，矩阵乘法）

算法竞赛进阶指南，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 */