11440번

11440번 - 피보나치 수의 제곱의 합

참고용 게시판에 피보나치 수열의 특징에 대한 글이 있다.

그 글을 읽고나서 피보나치와 관련된 문제를 풀면 훨씬 수월하다.

피보나치 수열의 제곱의 합(1~N까지) 은  F[N]*F[N+1] 이라는 것을 구할 수 있다.

이를 행렬의 곱과 활용하여 이용하면 된다.

<정답 코드>

#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;
    matrix A = calc(F, n);
    long long ans = ((A[0][0] % mod)*(A[0][1] % mod)) % mod;
    printf("%lld\n", ans);
 
    return 0;
}