回想起以前從事ACM活動，每當有一些題目做不出來，總是會去網(wǎng)上找別人的解題報告。可是
這些解題報告不是寫給人看的：一句dp，二分，線段樹，然后直接就貼了代碼，而且為了追求效率，這些代碼做的優(yōu)化都很大程度增加了閱讀的難度。比如不寫函數(shù)。
poj3070
這道題的意思是通過矩陣的冪來求Fibonacci數(shù)列的第n項，且只要求出它的后4位數(shù)。
先貼出我認為寫的還是比較清晰的代碼：
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)這兩個數(shù)相乘得到的后四位數(shù)是由b，d決定的。那么每次取模也就不影響后四位數(shù)了。
在做冪的時候其實體現(xiàn)的就是二分的思想，這可以算是計算機科學中最重要的思想之一了。
其實像我這樣的小菜是有多么希望那些牛人可以花點時間把自己對一道題的理解和思路寫出來，你可以不必每道題都寫出詳細的解題報告，但是你可以在那道沒有人寫詳細思路題上花點時間，這樣可以幫助到很多人！