백준 11524번: Immortal Porpoises

www.acmicpc.net/problem/11524

11524번: Immortal Porpoises

---

본문이 매우 깁니다.

 

핵심 문장은 가장 마지막에 있는데,

 

$ \cdots $ In fact, for any given year, Y, the number of living porpoise pairs is fib(Y) mod $ 10^{9} $, where fib(Y) is the Yth value in the well-known Fibonacci sequence.

 

한 마디로 Y번째 피보나치 수의 mod $ 10^{9} $ 값을 출력해주면 됩니다. 이전 글과 거의 같습니다.

(2021/01/29 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 11444번: 피보나치 수 6)

 

약간 다른 점으로는 최대 1000개의 피보나치 수( mod $ 10^{9} $ )를 출력해야 하는데

 

N번째 피보나치 수를 대략 $ O \left ( logN \right ) $ 에 구하기 때문에 시간은 전혀 문제가 없습니다.

 

#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, 제출번호 25776011)

---

이 문제의 경우 modulo 값이 $ 10^{9} $ 이므로, 피사노 주기를 이용하기는 힘들지 않을까 싶습니다.

(주기가 아마 $ 15\times 10^{8} $ 인데, 이걸 배열에 전부 저장한다고 하면 메모리는 몰라도 시간은 초과할 듯 합니다.)

 

언어가 영어인데다가, 문제도 다른 문제들과 차별점이 없고, 본문의 길이가 길이라서 인기가 없을 수밖에 없는 문제였습니다.

 

저도 여러번 본문을 다 읽어보려다가 말았습니다...