피 보 나치 수열 최적화 매트릭스 구법 실례

프로 그래 밍 문 제 를 풀 때'피 보 나치 수열'과 관련 된 문 제 를 자주 만 나 는데 특히 OJ 를 하 는 중 입 니 다.다음은 방법 을 말씀 드 리 겠 습 니 다.
(1)귀속
재 귀 는 가장 느 린 것 으로 중복 계산 이 발생 하고 시간 복잡 도 는 지수 급 이다.

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)순환
임시 변 수 를 이용 하여 중간의 계산 과정 을 저장 하고 연산 을 가속 화 합 니 다.

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)매트릭스 곱셈+공간 교환 시간(곱셈 감소,모드 연산)
 수열 의 전달 공식 은 f(1)=1,f(2)=2,f(n)=f(n-1)+f(n-2)(n>=3)이다.
행렬 로 표시:
 
더 나 아가 직접 유도 공식 을 얻 을 수 있다.
 
 행렬 곱셈 이 결합 율 을 만족 시 키 기 때문에 프로그램 에서 행렬 의 64,32,16,8,4,2,1 차방 을 미리 정 하여 프로그램의 집행 시간 을 가속 화 할 수 있다.(어떤 문 제 는 모형 연산 이 필요 하고 사전에 진행 할 수도 있다.주어진 행렬 차 멱 은 이 진 과 관련 이 있 는 이 유 는 다음 과 같은 공식 에 해 가 존재 하여 Xi={0 또는 1}을 만족 시 키 기 때 문 입 니 다.
Xi={0 또는 1}을 만족 시 키 기 위해 상기 공식 에 대한 구 해 는 오른쪽 에서 왼쪽으로,즉 구 해 순 서 는 Xn,Xn-1,Xn-2,...,X1,X0 이다.
전체 코드 는 다음 과 같 습 니 다.

///  fac(n)%100000，  n     3    
#include<stdio.h>
#include<math.h>
long long fac_tmp[6][4]={   ///      
                    ///  ：00 01 10 11
                   {24578,78309,78309,46269},   ///32  %100000
                   {1597,987,987,610},  ///16  %100000
                   {34,21,21,13},   ///8  %100000
                   {5,3,3,2},   ///4  %100000
                   {2,1,1,1},   ///2  %100000
                   {1,1,1,0},   ///1  %100000
                   };
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;  ///     1  
    long long a,b,c,d;
    k=k-3;  ///    n-2  ，(t00,t01,t10,t11)  1  。     3 
    for(i=k;i>=32;i=i-32)   ///      32 k;
    {
        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)    ///    32 k(16,8,4,2,1);
    {
        if(k>=(long long)pow(2,i))  ///  k     2   
        {
            a=(t00*fac_tmp[5-i][0]+t01*fac_tmp[5-i][2])%100000; ///(5-i)：   2 i     fac_tmp     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("%lld
",a);
}