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