백준 7677: Fibonacci

 

 

www.acmicpc.net/problem/7677

7677번: Fibonacci

---

문제에서 친절하게 어떤 행렬을 n 제곱하면 $F_{n}$이 나오는지, 잘 설명해주었습니다.

 

따라서 기본 이론2 에서 작성한 바와 같이 접근해주면 됩니다.

(2021/01/23 - [분할 정복을 이용한 거듭제곱] - 기본 이론2)

 

그러나 특이사항으로 "마지막 4자리"를 출력해주어야 합니다.

 

이는 mod 10000을 구하라는 뜻으로, 본문에도 정확히 나와있습니다.

(If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

 

코드는 다음과 같습니다.

 

#include <stdio.h>

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

int add_modular (int x, int y, int M);
int multiply_modular (int x, int y, int M);

Matrix matrix_multiply_modular (Matrix A, Matrix B, int M); // 2by2
Matrix matrix_power_modular (Matrix A, int k, int 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;
	
	int test;
	scanf("%d", &test);
	while (test != -1) {
		Matrix Fibonacci = matrix_power_modular (Base, test, 10000);
		printf("%d\n", Fibonacci.array[0][1]);
		scanf("%d", &test);
	}
	
	return 0;
}

int add_modular (int x, int y, int M) {
	x %= M;
	y %= M;
	if (x >= M - y || y >= M - x) {
		return (x - M) + y;
	}
	else {
		return x + y;
	}
}

int multiply_modular (int x, int y, int M) {
	x %= M;
	y %= M;
	int result = 0;
	while (y > 0) {
		if (y & 1) {
			result = add_modular (result, x, M);
		}
		x = add_modular (x, x, M);
		y >>= 1;
	}
	return result;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int 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++) {
				int temp = multiply_modular(A.array[i][k], B.array[k][j], M);
				result.array[i][j] = add_modular (result.array[i][j], temp, M);
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, int k, int 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, 4ms입니다. (제출 번호 25519576)

 

본문에서 처음부터 $2\times 2$ 행렬을 주었으므로, Matrix 구조체 안에 $2\times 2$ 배열을 집어넣었습니다.

 

그리고 본문에서 준 행렬 $\begin{pmatrix}
1 & 1\\ 
1 & 0
\end{pmatrix}$ 을 Base라고 하였습니다.

 

하지만 int 범위 안에서 해결한답시고 add_modular, multiply_modular 함수를 쓸데없이 구현하느라

 

분량도 길어지고 시간도 지체된 감이 있는 것 같습니다. (M이 10000이니까 굳이 구현할 필요가 없습니다.)

 

따라서 다음과 같이 수정했습니다. (2021/4/4)

 

#include <stdio.h>
#define mod 10000

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

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, int k);

int main() {
	
	Matrix Base = { {{1,1},{1,0}} };
	Base.array[0][0] = 1, Base.array[0][1] = 1, Base.array[1][0] = 1, Base.array[1][1] = 0;
	
	int test;
	scanf("%d", &test);
	while (test != -1) {
		Matrix Fibonacci = matrix_power_modular (Base, test);
		printf("%d\n", Fibonacci.array[0][1]);
		scanf("%d", &test);
	}
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B) { // 2by2
	Matrix result = { {{0,0}, {0,0}} };
	for (int i = 0; i <= 1; i++) {
		for (int k = 0; k <= 1; k++) {
			for (int j = 0; j <= 1; j++) {
				int temp = A.array[i][k] * B.array[k][j] % mod;
				result.array[i][j] = (result.array[i][j] + temp) % mod;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, int k) { // 2by2
	Matrix result = { {{1,0}, {0,1}} };
	while (k > 0) {
		if (k % 2) {
			result = matrix_multiply_modular (result, A);
		}
		A = matrix_multiply_modular (A, A);
		k /= 2;
	}
	return result;
}

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

---

본문에 어떤 행렬을 N제곱하면 될지, 그리고 modulo로 무슨 값을 쓰면 될지 다 나와있어서,

 

사실 골드3 보다는 낮은 평가를 받아도 할 말은 없어보입니다.

 

예를 들어 10830번과 같은 골드4 에 위치했더라도 납득할 수 있을 것 같습니다.