HDU　1005 Number Sequence

思路：快速冪乘+矩陣乘法
是個不錯的矩陣乘法練手的題目^0^...
其中有：
|  f(1)  f(2) |      |   0   B  |^(n-1)             |   f(n)        f(n+1)   |
|                |  *  |             |               =     |                            |
|  f(2)  f(3) |      |   1   A  |                       |    f(n+1)   f(n+2)  |

(圖片沒傳上，這個將就一下吧)

[cpp] 
#include<iostream> 
#include<cstdio> 
using namespace std; 
struct Matrix 
{ 
  int row[2][2]; 
}; 
Matrix num,rex,ans; 
int a,b,n; 
void Init() 
{ 
   num.row[0][0]=0;rex.row[0][0]=1; 
   num.row[0][1]=b;rex.row[0][1]=1; 
   num.row[1][0]=1;rex.row[1][0]=1; 
   num.row[1][1]=a;rex.row[1][1]=(a+b)%7; 
 
} 
 
Matrix MatrixMul(Matrix t1,Matrix t2) 
{ 
  Matrix sum; 
  int i,j; 
  for(i=0;i<2;i++) 
      for(j=0;j<2;j++) 
          sum.row[i][j]=(t1.row[i][0]*t2.row[0][j]+t1.row[i][1]*t2.row[1][j])%7; 
  return sum; 
} 
 
void Getdata(int teams) 
{ 
      ans=num; 
      while(teams) 
      { 
      if(teams&1) rex=MatrixMul(rex,ans); 
      ans=MatrixMul(ans,ans); 
      teams>>=1; 
      }   
} 
 
int main() 
{ 
   while(scanf("%d%d%d",&a,&b,&n)!=EOF&&(a||b||n)) 
   { 
      Init(); 
      Getdata(--n); 
      printf("%d\n",rex.row[0][0]); 
   } 
   return 0; 
} 

此外還一些小技巧也可以解決AC它
1。由題目的式子可知0<=f[n]<=6,
2。而每個f[n]又是由(f[n-1],f[n-2])這個組合通過計算得出來的,
由以上兩點可以推出,(f[n-1],f[n-2])出現重復的組合的最大周期為7*7=49, 即f[n]的最大周期
所有, 我們只要算出一個周期中所有的f[n]的值並記錄下周期i即可.
下面給出別人的代碼以供參考：

[cpp] 
#include<stdio.h> 
int main() 
{ 
    int a,b,n,i,f[53]; 
    while(scanf("%d%d%d",&a,&b,&n)!=EOF) 
    { 
        if(a==0 && b==0 && n==0) 
            break; 
        if(n==1 || n==2) 
        { 
            puts("1"); 
            continue; 
        } 
        f[1]=1,f[2]=1; 
        a%=7,b%=7; 
        for(i=3;i<=52;i++) 
        { 
            f[i]=(a*f[i-1]+b*f[i-2])%7; 
            if(f[i-1]==1 && f[i]==1) 
                break; 
        } 
        i-=2; 
        n%=i; 
        f[0]=f[i]; 
        printf("%d/n",f[n]); 
    } 
    return 0; 
}