[백준 11440] 피보나치 수의 제곱의 합

문제 링크 => 11440번: 피보나치 수의 제곱의 합 (acmicpc.net)

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

---

수학 + 분할 정복을 이용한 거듭제곱의 문제이다.

 

이문제는 2086번: 피보나치 수의 합 (acmicpc.net) 이걸 해결한다면 굉장히 쉬운 문제이다.

 

생각보다 이문제는 규칙성이 너무 쉽게 발견되서 금방 해결한 문제이기도 하다.

 

다음과 같이 규칙성을 찾아보도록 한다.

(이때 Fibo(1)^2 = 1, Fibo(2)^2 = 1, Fibo(3)^2 = 4, Fibo(4)^2 = 9, Fibo(5)^2 = 25, Fibo(6)^2 = 64, Fibo(7)^2 = 169, ... )

• n=1 => 1 = 1 - 1 + 1
• n=2 => 2 = 4 - 1 - 1
• n=3 => 6 = 9 - 4 + 1
• n=4 => 15 = 25 - 9 - 1
• n=5 => 40 = 64 - 25 + 1
• n=6 => 104 = 169 - 64 - 1
• ...

이쯤하면 규칙성이 딱 보이는 것을 알 수 있다.

 

첫번째로 n이 홀수이면 뒤에 +1, 짝수이면 뒤에 -1 이 붙는다는 것을 확인할 수 있다.

 

두번째로 +1, -1 상관없이 Fibo(1)^2+...+Fibo(n)^2 = Fibo(n+1)^2 - Fibo(n)^2 + a (a = 1 or -1) 임을 확인할 수 있다.

 

이것을 일반화한다면, 다음과 같다.

 

Fibo(1)^2+...+Fibo(n)^2 = Fibo(n+1)^2 - Fibo(n)^2 + (-1)^(n+1)

 

큰 수에 대한 피보나치 값은 [백준 2086] 피보나치 수의 합 :: M - J - C (tistory.com) 여기서 간단하게 확인하면 된다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

map<long long, long long> m[2];

long long fibo(long long x,int idx) {
	if (x == 0) return 0;
	if (x == 1) return 1;
	else if (x == 2) return 1;
	if (m[idx][x]) return m[idx][x];
	if (x % 2 == 0) {
		long long tmp1 = fibo(x / 2 + 1, idx) % 1000000007;
		long long tmp2 = fibo(x / 2 - 1, idx) % 1000000007;
		tmp1 = tmp1 * tmp1 % 1000000007;
		tmp2 = tmp2 * tmp2 % 1000000007;
		return m[idx][x] = (tmp1-tmp2+1000000007) % 1000000007;
	}
	else {
		long long tmp1 = fibo(x / 2, idx) % 1000000007;
		long long tmp2 = fibo(x / 2 + 1, idx) % 1000000007;
		tmp1 = tmp1 * tmp1 % 1000000007;
		tmp2 = tmp2 * tmp2 % 1000000007;
		return m[idx][x] = (tmp1 + tmp2) % 1000000007;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	long long n;
	cin >> n;
	long long tmp1 = fibo(n + 1, 0);
	long long tmp2 = fibo(n, 1);
	tmp1 = tmp1 * tmp1 % 1000000007;
	tmp2 = tmp2 * tmp2 % 1000000007;
	long long result = tmp1 - tmp2 + (n%2==0?-1:1);
	cout << (result + 1000000007) % 1000000007;

	return 0;
}