백준 13075번: Fibonacci Sequence

www.acmicpc.net/problem/13075

13075번: Fibonacci Sequence

---

이전에 올렸던 Immortal Porpoises 문제를 읽고 이 글을 읽어보면 뭔가 기시감이 들 겁니다.

 

T의 범위, X의 범위, 심지어 modulo 값까지 모두 일치합니다.

 

예제마저도 정확히 똑같은 값으로 주는데요, 이쯤되면 두 문제의 차이는 스토리텔링이 있느냐 없느냐 밖에 없습니다.

 

일단 코드입니다.

 

#include <stdio.h>

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

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M);
Matrix matrix_power_modular (Matrix A, long long K, long long M);

long long Get_Fibonacci (long long N);

int main() {
	
	int t;
	scanf("%d", &t);
	
	long long N;
	
	int i;
	for (i = 0; i < t; i++) {
		scanf("%lld", &N);
		printf("%lld\n", Get_Fibonacci(N));
	}
	
	return 0;
}

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

long long Get_Fibonacci (long long N) {
	Matrix Base;
	Base.array[0][0] = Base.array[0][1] = Base.array[1][0] = 1;
	Base.array[1][1] = 0;
	Base = matrix_power_modular (Base, N, 1000000000);
	return Base.array[0][1];
}

 

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

---

11524번과 완전히 같은 문제인데도 티어가 갈렸는데

 

개인적으로는 스토리텔링과 영어의 압박이 있는 11524번이 티어가 더 높아야 하지 않나 생각해봅니다.