백준 12728번: n제곱 계산

www.acmicpc.net/problem/12728

12728번: n제곱 계산

---

이전에 올렸던 글과 비교했을 때 $n$ 의 범위가 조금 더 커졌습니다. (백준 12925번: Numbers)

 

그 외의 차이가 없습니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>

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

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

int main() {
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		
		int N;
		scanf("%d", &N);
		
		printf("Case #%d: ", i);
		
		if (N == 2) {
			printf("027\n");
			continue;
		}
		
		Matrix Base;
		Base.array[0][0] = 0, Base.array[0][1] = 1, Base.array[1][0] = -4, Base.array[1][1] = 6;
		
		Matrix Answer;
		Answer.array[0][0] = 6, Answer.array[1][0] = 28;
		Answer.array[0][1] = Answer.array[1][1] = 0;
		
		int power = N - 2;
		Base = matrix_power_modular (Base, power);
		Answer = matrix_multiply_modular (Base, Answer);
		
		int answer = Answer.array[1][0] - 1;
		if (answer == 0) {
			printf("000\n");
		}
		else if (answer < 10) {
			printf("00%d\n", answer);
		}
		else if (answer < 100) {
			printf("0%d\n", answer);
		}
		else {
			printf("%d\n", answer);
		}
	}
	return 0;
}

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

Matrix matrix_power_modular (Matrix A, int power) {
	Matrix result;
	result.array[0][0] = result.array[1][1] = 1;
	result.array[1][0] = result.array[0][1] = 0;
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular (result, A);
		}
		A = matrix_multiply_modular (A, A);
		power /= 2;
	}
	return result;
}

 

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

---

이 문제의 출처는 Google Code Jam 2008 Round 1A의 C2번이었습니다.

 

이전글에 언급했던 "$n$이 충분히 작을 때"에 해당하는 문제가 "Numbers(small)" 이라는 제목으로 백준에 존재합니다.

 

(www.acmicpc.net/problem/12727)

 

$O\left ( N \right )$으로 구하면 충분합니다...

 

그런데, 정작 12925번 Numbers는 출처가 없네요. 어찌된 일인지 살짝 궁금해집니다.