回想起以前从事ACM活动，每当有一些题目做不出来，总是会去网上找别人的解题报告。可是
这些解题报告不是写给人看的：一句dp，二分，线段树，然后直接就贴了代码，而且为了追求效率，这些代码做的优化都很大程度增加了阅读的难度。比如不写函数。
poj3070
这道题的意思是通过矩阵的幂来求Fibonacci数列的第n项，且只要求出它的后4位数。
先贴出我认为写的还是比较清晰的代码：
1 #include<iostream>
2 using namespace std;
3 class matrix{
4 public:
5 int a[2][2];
6 matrix(){
7 a[0][0]=a[0][1]=a[1][0]=1;
8 a[1][1]=0;
9 }
10 };
11 //矩阵的乘法
12 matrix multi(matrix a,matrix b){
13 matrix temp;
14 for(int i = 0; i < 2; i++)
15 for(int j = 0; j < 2; j++){
16 temp.a[i][j] = 0;
17 for(int k = 0; k < 2;k++)
18 temp.a[i][j] += a.a[i][k]*b.a[k][j];
19 if(temp.a[i][j] >= 10000)
20 temp.a[i][j] %= 10000;//注释1
21 }
22 return temp;
23 }
24 //矩阵的n次幂
25 matrix power(int n){
26 matrix temp,s;
27 temp.a[1][0] = temp.a[0][1] = 0;
28 temp.a[1][1] = 1;//把temp化成单位矩阵
29 while(n != 0){
30 if(n & 1)
31 temp = multi(temp,s);
32 n = n >> 1;
33 s = multi(s,s);
34 }
35 return temp;
36 }
37 int main(){
38 int n;
39 while(cin >> n && n != -1){
40 matrix ans = power(n);
41 cout << ans.a[1][0] << endl;
42 }
43 }
44
45
46
47
注释1：为什么可以在每次乘法的取模呢？这是因为：(a*10000+b)*(c*10000+d)，即(a*10000+b)和(c*10000+d)这两个数相乘得到的后四位数是由b，d决定的。那么每次取模也就不影响后四位数了。
在做幂的时候其实体现的就是二分的思想，这可以算是计算机科学中最重要的思想之一了。
其实像我这样的小菜是有多么希望那些牛人可以花点时间把自己对一道题的理解和思路写出来，你可以不必每道题都写出详细的解题报告，但是你可以在那道没有人写详细思路题上花点时间，这样可以帮助到很多人！