题意：求斐波那契数列第n项值（mod 10000），但n可达1,000,000,000。
题目链接：http://poj.org/problem?id=3070
——>>斐波那契数的题还可真是多，最先碰到的可在64位整数内打表过掉，接着碰到得用高精度来计算的大斐波数，到现在这道须用矩阵快速幂来计算的超大n……
#include <cstdio>using namespace std;const int mod = 10000;
struct Mar //定义矩阵类型
{int a[2][2];Mar(){a[0][0] = 1; a[0][1] = 1;a[1][0] = 1; a[1][1] = 0;}Mar(int a1, int a2, int b1, int b2){a[0][0] = a1; a[0][1] = a2;a[1][0] = b1; a[1][1] = b2;}
};
Mar mul(Mar e1, Mar e2) //矩阵乘法
{int a1 = (e1.a[0][0]*e2.a[0][0] + e1.a[0][1]*e2.a[1][0]) % mod;int a2 = (e1.a[0][0]*e2.a[0][1] + e1.a[0][1]*e2.a[1][1]) % mod;int b1 = (e1.a[1][0]*e2.a[0][0] + e1.a[1][1]*e2.a[1][0]) % mod;int b2 = (e1.a[1][0]*e2.a[0][1] + e1.a[1][1]*e2.a[1][1]) % mod;return Mar(a1, a2, b1, b2);
}
Mar dfs(Mar cur, int x) //求cur的x次幂
{if(x == 1) return cur;Mar temp = dfs(cur, x / 2); //二分if(x % 2 == 0)return mul(temp, temp);elsereturn mul(mul(temp, temp), cur);
}
int main()
{int n;while(~scanf("%d", &n)){if(n == -1) return 0;if(!n )printf("0\n");else if(n == 1) printf("1\n");else{Mar ret = dfs(Mar(), n-1);printf("%d\n", ret.a[0][0]);}}return 0;
}