백준 14440번: 정수 수열

 

www.acmicpc.net/problem/14440

14440번: 정수 수열

---

이전글 (백준 11366번: Tons of Orcs, no Fibbin') 이 기존 피보나치 수열에서 $ F_{0} $ 과 $ F_{1} $ 을 변형한 것이라면,

 

이번 문제는 $ A_{n+2}=x\times A_{n+1}+y\times A_{n} $ 으로, 피보나치 수열이 증가하는 규칙을 변형한 것입니다.

 

따라서, 다음 식과 같이 풀면 됩니다. (이때 $ x=y=1 $ 인 경우가 기존의 피보나치 수열)

 

$ \begin{pmatrix} A_{n+1} & A_{n} \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} A_{1} & A_{0} \\ 0 & 0 \end{pmatrix} \times \begin{pmatrix} x & 1 \\ y & 0 \end{pmatrix}^{n} $

 

그런데 A0와 A1이 "두 자리"로 입력되는 점과, "맨 끝의 두 자리"를 출력해야 하는 점을 주의해야 합니다.

 

단순히 mod 100을 적용하여 구하면 "08"로 출력되어야하는 것이 "8"로 출력되는 등의 문제가 생길 수 있기 때문입니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>

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

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

int main() {
	
	int x, y;
	char a0[3], a1[3];
	long long n;
	scanf("%d %d %s %s %lld", &x, &y, a0, a1, &n);
	
	int A0 = 10*(a0[0] - '0') + (a0[1] - '0');
	int A1 = 10*(a1[0] - '0') + (a1[1] - '0');
	
	Matrix Base;
	Base.array[0][0] = x, Base.array[1][0] = y, Base.array[0][1] = 1, Base.array[1][1] = 0;
	
	Matrix answer;
	answer.array[0][0] = A1, answer.array[0][1] = A0;
	answer.array[1][0] = answer.array[1][1] = 0;
	
	Base = matrix_power_modular (Base, n, 100);
	answer = matrix_multiply_modular (answer, Base, 100);
	
	int temp = answer.array[0][1];
	
	char result[3];
	result[0] = '0' + (temp / 10);
	result[1] = '0' + (temp % 10);
	result[2] = '\0';
	
	printf("%s", result);
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int 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++) {
				int 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, int M) {
	Matrix result;
	result.array[0][0] = result.array[1][1] = 1;
	result.array[1][0] = result.array[0][1] = 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;
}

 

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

---