피보나치 수열 문제의 귀착과 동태 기획 3

피보나치 수열 문제의 귀착과 동태 기획 3
제목 설명
농장에서 성숙한 암소가 해마다 한 마리의 암소만 낳고 영원히 죽지 않는다고 가정하자.첫해 농장에는 성숙한 암소 한 마리가 있었고, 이듬해부터 암소가 새끼를 낳기 시작했다.암소 한 마리당 3년 후에 익으면 암소를 낳을 수 있다.정수 n을 정하여 n 년 후의 소의 수량을 구하다.
설명 입력:
정수 n 을 입력합니다.
출력 설명:
n년 후 소의 수량을 1e9+7로 출력하는 값.
예제 1
입력

6

출력

9

참고:
1 ≤ n ≤ 1 0 18 1\leq n\leq 10^{18} 1≤n≤1018
문제 풀이:
점차적 공식: F(n) = F(n -3) + F(n -3) F(n) = F(n -1) + F(n -3) F(n) = F(n -3) + F(n -1) + F(n -3)는 3단계 점차적 수열로 행렬 곱셈은 [F(n) F(n -3) F(n -1) F(n -4 2) = [F(n -4 1) F(n -4 2) F(n -4 2) F(n -3)]× [ 1 1 0 0 0 1 1 0 0 ]\left[\begin{matrix} F(n) & F(n-1) & F(n-2\end{matrix}\right] =\left[\begin{matrix}F(n-1) & F(n-2) & F(n-3)\end{matrix}\right]\times\left[\begin{matrix} 1 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\end{matrix}\right] [F(n)​F(n−1)​F(n−2​]=[F(n−1)​F(n−2)​F(n−3)​]×⎣⎡​101​100​010​⎦⎤​
. . . ... ...
[ F ( n ) F ( n − 1 ) F ( n − 2 ] = [ F ( 3 ) F ( 2 ) F ( 1 ) ] × [ 1 1 0 0 0 1 1 0 0 ] n − 3\left[\begin{matrix} F(n) & F(n-1) & F(n-2\end{matrix}\right] =\left[\begin{matrix}F(3) & F(2) & F(1)\end{matrix}\right]\times\left[\begin{matrix} 1 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\end{matrix}\right]^{n-3} [F(n)​F(n−1)​F(n−2​]=[F(3)​F(2)​F(1)​]×⎣⎡​101​100​010​⎦⎤​n−3
코드:

#include 
#include 

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;

LL n;
LL tmp[3][3];

void mat_mul(LL ret[][3], LL ans[][3]) {
     
    memset(tmp, 0LL, sizeof tmp);
    for (int i = 0; i < 3; ++i) {
     
        for (int j = 0; j < 3; ++j) {
     
            for (int k = 0; k < 3; ++k) {
     
                tmp[i][j] += ret[i][k] * ans[k][j] % MOD;
                tmp[i][j] %= MOD;
            }
        }
    }
    memcpy(ret, tmp, sizeof tmp);
}

void solve(LL n) {
     
    LL ret[][3] = {
     {
     1,0,0},{
     0,1,0},{
     0,0,1}};
    LL ans[][3] = {
     {
     1,1,0},{
     0,0,1},{
     1,0,0}};
    while (n) {
     
        if (n & 1LL) mat_mul(ret, ans);
        mat_mul(ans, ans);
        n >>= 1LL;
    }
    printf("%lld
", (3 * ret[0][0] + 2 * ret[1][0] + ret[2][0]) % MOD);
}

int main(void) {
     
    scanf("%lld", &n);
    if (n < 4LL) return 0 * printf("%lld
", n);
    solve(n - 3LL);
    return 0;
}