11443번

11443번 - 짝수번째 피보나치 수의 합

홀수번째 피보나치 수의 합과 비슷한 방식으로 증명해가면서 풀었다.

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

짝수의 합을 만들어 내기 위해 N 대신 2N-1 을 대입해서 세개중 하나만 짝수로 만들어서 증명했다.

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

1~2N 까지 짝수번째 피보나치 수의 합은 F[2N+1] - 1이 된다.

입력으로 주어지는 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 == 1)
    {
        matrix A = calc(F, n);
        long long ans = ((A[0][1] % mod) -1 + mod) % mod;
        printf("%lld\n", ans);
    }
    else
    {
        matrix A = calc(F, n+1);
        long long ans = ((A[0][1] % mod)-1+mod) % mod;
        printf("%lld\n", ans);
    }
 
 
    
 
    
 
    return 0;
}