An example of Fibonacci sequence optimization matrix method

When doing programming problems, you often encounter problems related to the Fibonacci sequence, especially when doing OJ. Here are some ways:

(1) recursion

Recursion is the slowest and then you have double counting, exponential time complexity.

long long fac(int n)
{
　　if(n==1) 　　return 1;
　　else if(n==2)  　return 2;
　　else   　return fac(n-1)+fac(n-2);
}

(2) circulation

Use temporary variables to save the middle of the calculation process, speed up the operation.

long long fac(int n)
{
    long long a=1,b=2,c;
    if(n==1)    return 1;
    else if(n==2)   return 2;
    else
    {
        for(int i=3;i<=n;i++)
        {
            c=a+b; 　　a=b; 　　b=c;
        }
    }
    return b;
}

(3) matrix multiplication + space change time (reduce multiplication, take modulus operation)

  The recursive formula of the sequence is: f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2)(n> = 3)

Represented by matrix:

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201303/2013319120707580.png" >

 

Further, the direct derivation formula can be obtained:

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201303/2013319120857622.png" >

 

  Since matrix multiplication satisfies the associative law, the execution time of the program can be accelerated by giving the matrix to the power 64,32,16,8,4,2,1 in advance. Some problems need to take the modulus of operation, you can also be done in advance. The given matrix power is related to binary because the following formula has a solution that satisfies Xi={0 or 1} :

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201303/2013319121024958.png" >

In order to ensure that the solution satisfies Xi={0 or 1}, the solution of the above formula is from right to left, that is, the order of solution is Xn, xn-1, xn-2... , the X1, X0.

The complete code is implemented as follows:

/// for fac(n)%100000, where n is a positive integer greater than or equal to 3
#include<stdio.h>
#include<math.h>
long long fac_tmp[6][4]={   /// store the matrix to the power
                    /// location: 00 01 10 11
                   {24578,78309,78309,46269},   /// 32 times power % 100000
                   {1597,987,987,610},  //16 / power % 100000
                   {34,21,21,13},   /// 8 times power % 100000
                   {5,3,3,2},   //Power % 100000/4 times
                   {2,1,1,1},   /// 2 times the power % 100000
                   {1,1,1,0},   /// power % 100000 at a time
                   };
void fac(int);
int main()
{
    int n;
    scanf("%d",&n);
    fac(n);
    return 1;
}
void fac(int k) ///k>=3
{
    int i;
    long long t00=1,t01=1,t10=1,t11=0;  /// is the matrix to the power of 1
    long long a,b,c,d;
    k=k-3;  /// n to the power of n minus 2, t00,t01,t10,t11. So we're going to subtract 3 times
    for(i=k;i>=32;i=i-32)   /// for k greater than or equal to 32;
    {
        a=(t00*fac_tmp[0][0]+t01*fac_tmp[0][2])%100000;
        b=(t00*fac_tmp[0][1]+t01*fac_tmp[0][3])%100000;
        c=(t10*fac_tmp[0][0]+t11*fac_tmp[0][2])%100000;
        d=(t10*fac_tmp[0][1]+t11*fac_tmp[0][3])%100000;
        t00=a;  t01=b;  t10=c;t11=d;
    }
    i=4;
    while(i>=0)    /// for k(16,8,4,2,1) less than 32;
    {
        if(k>=(long long)pow(2,i))  /// if k is greater than some power of 2
        {
            a=(t00*fac_tmp[5-i][0]+t01*fac_tmp[5-i][2])%100000; ///(5-i) : the position of the matrix 2 to the I in the array fac_tmp is fac_tmp[5-i]
            b=(t00*fac_tmp[5-i][1]+t01*fac_tmp[5-i][3])%100000;
            c=(t10*fac_tmp[5-i][0]+t11*fac_tmp[5-i][2])%100000;
            d=(t10*fac_tmp[5-i][1]+t11*fac_tmp[5-i][3])%100000;
            t00=a;  t01=b;  t10=c;t11=d;
            k=k-(int)pow(2,i);
        }
        i--;
    }
    a=(t00*2+t01*1)%100000;
    printf("%lldn",a);
}