11442번

11442번 - 홀수번째 피보나치 수의 합

홀수번째 피보나치 수의 합도 쉽게 구할 수 있다.

기존의 피보나치 식 F[N+2]=F[N]+F[N+1] 에서

하나만 홀수로 만들어서 정렬하여 증명을 하기 위해서 나는 N 대신 2N을 대입했다

(다른 분들 코드를 보니 2N-2 를 대입한 코드들이 많았다. )

그래서 F[2N+1] = F[2N+2]-F[2N] 을 이용해서 문제를 풀었다.

단, 이 문제에서 주의할 점은 입력으로 들어오는 N의 값이 홀수인지 짝수인지 파악해야 한다!

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
const long long mod = 1000000007;
typedef vector<vector<long long>> matrix;
matrix operator *(matrix &A, matrix &B)
{
    matrix ret(2, vector<long long>(2));
 
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            long long sum = 0;
            for (int m = 0; m < 2; m++)
            {
                sum += ((A[i][m]%mod) * (B[m][j]%mod))%mod;
            }
            ret[i][j] = sum%mod;
        }
    }
 
    return ret;
 
}
matrix calc(matrix &A, long long B)
{
    if (B == 0)
    {
        matrix ret(2, vector<long long>(2));
        ret[0][0] = 1, ret[0][1] = 0, ret[1][0] = 0, ret[1][1] = 1;
        return ret;
    }
    else if (B % 2 == 0)
    {
        matrix temp = calc(A, B / 2);
        return temp*temp;
    }
    else
    {
        matrix temp = calc(A, B - 1);
        return A*temp;
    }
 
}
int main()
{
    long long n;
    scanf("%lld", &n);
    matrix F(2, vector <long long>(2));
    F[0][0] = 1, F[0][1] = 1, F[1][0] = 1, F[1][1] = 0;
 
    if (n % 2 == 0)
    {
        matrix A = calc(F, n);
        long long ans = ((A[0][1] % mod)) % mod;
        printf("%lld\n", ans);
    }
    else
    {
        matrix A = calc(F, n+1);
        long long ans = ((A[0][1] % mod)) % mod;
        printf("%lld\n", ans);
    }
 
    
 
    return 0;
}