백준 11444번: 피보나치 수 6

 

 

www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

---

이전에 올렸던 피보나치 문제와 거의 같은 문제입니다.

(2021/01/23 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 7677: Fibonacci)

 

mod $ 10^{9}+7 $ 이므로 배열을 long long으로 선언해주기만 하면 충분합니다.

 

( $ \left ( 10^{9}+7 \right )^{2}<2^{63}-1 $ 이므로 )

 

#include <stdio.h>

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

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M); // 2by2
Matrix matrix_power_modular (Matrix A, long long k, long long M);

int main() {
	
	Matrix Base;
	Base.array[0][0] = 1, Base.array[0][1] = 1, Base.array[1][0] = 1, Base.array[1][1] = 0;
	
	long long n;
	scanf("%lld", &n);
	
	Matrix Fibonacci = matrix_power_modular (Base, n, 1000000007);
	printf("%lld", Fibonacci.array[0][1]);
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M) { // 2by2
	Matrix result;
	int i, j, k;
	for (i = 0; i <= 1; i++) {
		for (j = 0; j <= 1; j++) {
			result.array[i][j] = 0;
		}
	}
	for (i = 0; i <= 1; i++) {
		for (j = 0; j <= 1; j++) {
			for (k = 0; k <= 1; 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) { // 2by2
	Matrix result;
	result.array[0][0] = 1, result.array[0][1] = 0, result.array[1][0] = 0, result.array[1][1] = 1;
	while (k > 0) {
		if (k & 1) {
			result = matrix_multiply_modular (result, A, M);
		}
		A = matrix_multiply_modular (A, A, M);
		k >>= 1;
	}
	return result;
}

 

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

---

이 문제는 어떤 행렬을 N제곱하면 답이 도출되는 지 제시되어 있지 않아서 배경지식의 난이도가 조금 있다고 생각합니다.

 

또 modulo 값이 $ 10^{9}+7 $ 이라 피사노 주기를 쓰기 꺼려지는 면이 있는데 solved ac 기여자 분들도 비슷한 관점인 것 같습니다.