백준 11440번: 피보나치 수의 제곱의 합

www.acmicpc.net/problem/11440

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

---

이 문제 역시 이전의 세 글과 같이 특정 성질을 이용하여 푸는 문제이지만, 그 성질이 비교적 유도가 힘든 것 같습니다.

(백준 11443번: 짝수번째 피보나치 수의 합 , 백준 11442번: 홀수번째 피보나치 수의 합 , 백준 2086번: 피보나치 수의 합)

 

때문에 다른 성질들과는 다르게 이번엔 유도과정을 조금 보여드리려 합니다.

 

$ F_{i}^{2}=F_{i}\times F_{i}=F_{i}\times \left ( F_{i+1}-F_{i-1} \right ) $ 이므로,

 

$ \sum_{i=1}^{n}F_{i}^{2}=\sum_{i=1}^{n}\left ( F_{i}F_{i+1}-F_{i}F_{i-1} \right )=F_{n}F_{n+1} $ 입니다.

 

이를 활용하여 다음과 같이 코드를 짰습니다.

 

#include <stdio.h>

typedef struct {
	long long array[2][2];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M);
Matrix matrix_power_modular (Matrix A, long long K, long long M);

long long Get_Fibonacci (long long N);

int main() {
	long long n;
	scanf("%lld", &n);
	long long result = (Get_Fibonacci(n) * Get_Fibonacci(n+1)) % 1000000007;
	printf("%lld", result); // F(i)^2 = F(i)F(i+1) - F(i)F(i-1) for i >= 1
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < 2; i++) {
		for (j = 0; j < 2; j++) {
			result.array[i][j] = 0;
			for (k = 0; k < 2; k++) {
				long long temp = (A.array[i][k] * B.array[k][j]) % M;
				result.array[i][j] = (result.array[i][j] + temp) % M;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, long long K, long long M) {
	Matrix result;
	result.array[0][0] = result.array[1][1] = 1;
	result.array[0][1] = result.array[1][0] = 0;
	while (K > 0) {
		if (K & 1) {
			result = matrix_multiply_modular (result, A, M);
		}
		A = matrix_multiply_modular (A, A, M);
		K >>= 1;
	}
	return result;
}

long long Get_Fibonacci (long long N) {
	Matrix Base;
	Base.array[0][0] = Base.array[0][1] = Base.array[1][0] = 1;
	Base.array[1][1] = 0;
	Base = matrix_power_modular (Base, N, 1000000007);
	return Base.array[0][1];
}

 

(C11, 1116KB, 0ms, 제출번호 25616955)

---

지금까진 피보나치 수의 특정 성질을 이용했을 뿐, 여전히 잘 알려진, 기존의 피보나치 수를 활용하는 문제들이었습니다.

 

다음 글로는 기존의 피보나치 수를 변형한 문제를 다룰 것 같습니다.