一、斐波那契数列F［n］＝F［n-1］+F[n-2]

    可转换为矩阵s［1，1，1，0］的n次幂的矩阵的s［0］［1］的值

    矩阵的幂次方 可通过 奇判断及进制移位提高时间效率

   位与运算 n&1表示的意思：取二进制n的最末位，二进制的最末位为零表示n为哦数，为1表示奇数，即等价于n％2

   n>>1 是将n的二进制向右移动一位， n>>=1 即把移动后的值赋给n 

 题目：求斐波那契数列F[n]%10000(取模)

#include 
     
      #include 
      
       using namespace std;const int MOD = 10000;int fast_mod(int n)    // 求 (t^n)%MOD {    int t[2][2] = {
   1, 1, 1, 0};    int ans[2][2] = {
   1, 0, 0, 1};  // 初始化为单位矩阵    int tmp[2][2];    //自始至终都作为矩阵乘法中的中间变量          while(n)    {        if(n & 1)  //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t         {            for(int i = 0; i < 2; ++i)                for(int j = 0; j < 2; ++j)                    tmp[i][j] = ans[i][j];             ans[0][0] = ans[1][1] = ans[0][1] = ans[1][0] = 0;  // 注意这里要都赋值成 0                         for(int i = 0; i < 2; ++i)    //  矩阵乘法             {                for(int j = 0; j < 2; ++j)                {                    for(int k = 0; k < 2; ++k)                        ans[i][j] = (ans[i][j] + tmp[i][k] * t[k][j]) % MOD;                }            }        }                //  下边要实现  t *= t 的操作，同样要先将t赋值给中间变量  tmp ，t清零，之后 t = tmp* tmp         for(int i = 0; i < 2; ++i)            for(int j = 0; j < 2; ++j)                tmp[i][j] = t[i][j];        t[0][0] = t[1][1] = 0;        t[0][1] = t[1][0] = 0;        for(int i = 0; i < 2; ++i)        {            for(int j = 0; j < 2; ++j)            {                for(int k = 0; k < 2; ++k)                    t[i][j] = (t[i][j] + tmp[i][k] * tmp[k][j]) % MOD;            }        }                n >>= 1;    }    return ans[0][1];}int main(){    int n;    while(scanf("%d", &n) && n != -1)    {            printf("%d\n", fast_mod(n));    }    return 0;}
      
     

二、斐波那契数列的衍生数列

根据斐波那契数列的矩阵法，得到此题 的结果应为s[2][2]={1,8,1,0}的n－2次幂的矩阵的s［0］［0］＋s［0］［1］的值

#include
     
      const long long MOD=100000007;using namespace std;int main(){    long long n,h;    int i,j,k;    while(cin>>n)    {        long long f[2][2]={
   1,0,0,1};        long long s[2][2]={
   1,8,1,0};        long long t[2][2];        if(n==1||n==2)            cout<<1<
      
       >=1;        }        h=(f[0][0]+f[0][1])%MOD;        cout<
       
        <