当要求递推数列的第n项且n很大时，怎么快速求得第n项呢?

可以用矩阵快速幂来加速计算。

我们可以用矩阵来表示数列递推公式

比如fibonacci数列 可以表示为 [f(n)   f(n-1)] = [f(n-1)    f(n-2)] [ 1 1 ]

　　　　　　　　　　　　　　　　　　　　　　　　　    　[ 1 0 ] 

设A = [ 1 1 ]

　　  [ 1 0 ]

[f(n)   f(n-1)] = [f(n-2)   f(n-3)]*A*A

[f(n)   f(n-1)] = [f(2)   f(1)]*A^(n-2)

矩阵满足结合律，所以先计算A^(n-2)，这个可以用一般快速二分幂的思想来计算。

BestCoder Round#8 1002

当n为奇数时，f(n) = 2 * f(n-1) + 1

当n为偶数时，f(n) = 2 * f(n-1)

将偶数项独立出来形成单独的一个数列 b(2*n) = 2 * b(2*n-1) + 1 = 4 * (2*n-2) + 2

即b(n) = 4 * b(n-1) + 2

当n为偶数时，计算b(n/2)即可

当n为奇数时，计算b(n/2) * 2 + 1即可

因为n很大，可以用矩阵快速幂来加速

递推矩阵为 [b(n)   2] = [b(n-1]   2] * [ 4 0 ]

　　　　　　　　　　　　　  　     [ 1 1 ]

 

1 #include 
      
        2 #include 
       
         3 typedef long long LL; 4 struct Matrix 5 { 6     LL matrix[2][2]; 7 }; 8 int n,m; 9 Matrix operator *(const Matrix &lhs, const Matrix &rhs)10 {11     Matrix res;12     memset(res.matrix, 0 ,sizeof(res.matrix));13     int i,j,k;14     for(k=0; k<2; ++k)15         for(i=0; i<2; ++i)16         {17             if(lhs.matrix[i][k] == 0) continue;18             for(j=0; j<2; ++j)19             {20                 if(rhs.matrix[k][j] == 0) continue;21                 res.matrix[i][j] = (res.matrix[i][j] + lhs.matrix[i][k] * rhs.matrix[k][j]) % m;22             }23         }24     return res;25 }26 Matrix operator ^(Matrix a, int k)27 {28     Matrix res;29     int i,j;30     for(i=0; i<2; ++i)31         for(j=0; j<2; ++j)32             res.matrix[i][j] = (i == j);33     while(k)34     {35         if(k & 1)36             res = res * a;37         a = a * a;38         k>>=1;39     }40     return res;41 }42 43 int main()44 {45     while(scanf("%d%d",&n,&m)!=EOF)46     {47         Matrix a;48         a.matrix[0][0] = 4;49         a.matrix[0][1] = 0;50         a.matrix[1][0] = a.matrix[1][1] = 1;51         int k = n / 2;52         a = a ^ k;53         LL ans =(2 * a.matrix[1][0]) % m;54         if(n & 1 == 1)55             ans = (ans * 2 + 1) % m;56         printf("%lld\n",ans);57 58     59     }60     return 0;61 }