백준 11444번 C++ 풀이

문제

https://www.acmicpc.net/problem/11444

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 2

---

풀이

  피보나치 수열의 n번째 원소를 1000000007으로 나눈 나머지를 구하면 되는 아주 간단한(?) 문제이다. 단지 n이 최대 100경일 뿐이다...

누가 봐도 O(logN)으로 줄일 필요가 있어 보인다. 피보나치 수열은 행렬로도 나타낼 수 있다고 들은 기억이 있어 해당 정보를 통해 피보나치 수열의 행렬식을 찾아보았다. 피보나치 수열의 행렬식은 다음과 같다.

 

이전에 풀었던 빠른 행렬 제곱을 이용하면 n이 아무리 커도 O(logN)의 시간복잡도를 통해 행렬의 제곱을 구할 수 있다. 빠른 행렬 제곱에 대해서는 다음 글을 참조하자. https://codejin.tistory.com/280

백준 10830번 C++ 풀이

 

어쨌든 행렬식을 제곱하고 행렬의 (1, 2)원소 또는 (2, 1)원소의 값을 구하면 그것이 n번째 피보나치 수이다. 원소의 크기에 주의하여 long long으로 처리해주고, 모듈러 연산을 대입하면 된다.

코드

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;

class Matrix2D {
	vector<vector<ll>> mat;
	int row, col;
public:
	Matrix2D(int row = 0, int col = 0) {
		init(row, col);
	}

	Matrix2D(const vector<vector<ll>>& data) {
		this->row = (int)data.size();
		this->col = (int)data[0].size();
		mat = data;
	}

	void init(int row = 0, int col = 0) {
		this->row = row;
		this->col = col;
		this->mat.resize(row, vector<ll>(col, 0));
	}

	Matrix2D operator*(const Matrix2D& other) {
		ll r;
		Matrix2D tmp(this->row, other.col);

		for(int k = 0; k < this->col; k++) {
			for(int i = 0; i < this->row; i++) {
				r = mat[i][k];
				for(int j = 0; j < other.col; j++) {
					tmp.mat[i][j] += ((r % MOD) * (other.mat[k][j] % MOD)) % MOD;
					tmp.mat[i][j] %= MOD;
				}
			}
		}

		return tmp;
	}
	
	Matrix2D pow(ll a) {
		if (a == 1) return *this;

		Matrix2D tmp(pow(a / 2));

		if (a % 2 == 1) return (*this) * tmp * tmp;
		else return tmp * tmp;
	}

	ll getElem(int r, int c) { return mat[r][c]; }
};

int main() {
	cin.tie(0)->sync_with_stdio(false);
	vector<vector<ll>> fib = { {1, 1}, {1, 0} };
	ll n;

	cin >> n;
	cout << Matrix2D(fib).pow(n).getElem(1, 0);
}