BOJ 11444 피보나치 수 6

www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

이번에는 나누는 값이 1000000007이다. 

 

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

이 문제에서는 나누는 값이 백만이라 피사노 주기를 통해서 구할 수 있었지만 이번 문제에서는

• 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

조건 때문에 피사노 주기를 구하려면 시간 초과가 날 것이다.

따라서 행렬 거듭제곱에 대한 지식이 필요한데 행렬의 지식이 부족해서 유튜브를 뒤적거리다

좋은 영상을 발견했다.

www.youtube.com/watch?v=uX2IsIykLJc

이분 영상에서 피보나치 점화식을 행렬로 표현하는데, 조금 더 변형시켜서 

Fn+1 Fn        1  1

Fn Fn-1   은   1  0  의 제곱으로 나타낼 수 있다.

#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define vii vector<vector<ll>>
#define vi vector<ll>
#define MOD (int)1e6

vii operator* (const vii& a, const vii& b) {
	int sz = a.size();
	vii ret(sz, vi(sz));
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			for (int k = 0; k < sz; k++) {
				ret[i][j] += a[i][k] * b[k][j];
			}
			ret[i][j] %= MOD;
		}
	}
	return ret;
}

vii power(vii& a, ll b) {
	int sz = a.size();
	vii ret(sz, vi(sz));
	for (int i = 0; i < sz; i++) ret[i][i] = 1;

	while (b) {
		if (b % 2) ret = ret * a;
		b /= 2;
		a = a * a;
	}
	return ret;
}

int main() {
	ll n;
	cin >> n;
	vii A = { {1,1},{1,0} };

	vii ans = power(A, n);

	cout << ans[0][1] << endl;

	return 0;
}

행렬 제곱 문제를 풀었다면 쉽게 풀 수 있는 문제였다.