最近數據結構實習，2天沒做題了，真好今天又沒課，還是繼續上次的矩陣專題吧。。。

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2855

我一直在把這個公式矩陣化，可是搞了老半天也出不了結果，后來看了別人的思路，頓時豁然開朗了。。。

思路：

斐波那契數列可以用矩陣來表示：mat={1，1，1，0}，

故f[n]=mat^n;

而在組合數學中有（1+x)^n=,從而聯想到令x=mat，1為單位矩陣；

然后矩陣求冪就可以了；

View Code 1 #include<iostream> 2 using namespace std; 3 int n,m; 4 5 struct Matrix{ 6 int map[2][2]; 7 }; 8 Matrix mat,unit; 9 10 void Initiate(){ 11 mat.map[0][0]=2; 12 mat.map[0][1]=1; 13 mat.map[1][0]=1; 14 mat.map[1][1]=1; 15 unit.map[0][0]=unit.map[1][1]=1; 16 unit.map[0][1]=unit.map[1][0]=0; 17 } 18 19 Matrix Mul(Matrix &a,Matrix &b){ 20 Matrix c; 21 for(int i=0;i<2;i++){ 22 for(int j=0;j<2;j++){ 23 c.map[i][j]=0; 24 for(int k=0;k<2;k++){ 25 c.map[i][j]+=a.map[i][k]*b.map[k][j]; 26 c.map[i][j]%=m; 27 } 28 } 29 } 30 return c; 31 } 32 33 Matrix Pow(int n){ 34 Matrix p=unit,q=mat; 35 while(n){ 36 if(n&1) 37 p=Mul(p,q); 38 n>>=1; 39 q=Mul(q,q); 40 } 41 return p; 42 } 43 44 45 int main(){ 46 int _case; 47 scanf("%d",&_case); 48 Initiate(); 49 while(_case--){ 50 scanf("%d%d",&n,&m); 51 Matrix remat=Pow(n); 52 printf("%d\n",remat.map[0][1]); 53 } 54 return 0; 55 }

?

?

轉載于:https://www.cnblogs.com/wally/archive/2013/03/06/2945400.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的hdu 2855的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。