백준 27435번: 파도반 수열 2

https://www.acmicpc.net/problem/27435

27435번: 파도반 수열 2

---

파도반 수열의 초반 항이 10개 주어져있고, 그림도 친절하게 주어져있어 점화식을 추론하기 쉽습니다.

 

$$P(n) = P(n-1) + P(n-5)$$

 

이 점화식에 따르면 $5 \times 5$ 행렬 거듭제곱을 통해 빠르게 답을 구할 수 있게 됩니다.

 

$$ \begin{bmatrix} P(n+4) \\ P(n+3) \\ P(n+2) \\ P(n+1) \\ P(n) \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix}^{n} \begin{bmatrix} P(4) \\ P(3) \\ P(2) \\ P(1) \\ P(0) \end{bmatrix} $$

 

주어진 점화식과 주어진 초반 10개 항의 값에 따라 $P(0)=0$으로 놓을 수 있어 답이 결정됩니다.

 

그러나, 파도반 수열은 점화식이 하나 더 있습니다.

 

$$P(n) = P(n-2) + P(n-3)$$

 

이 식을 쓰면 $3 \times 3$ 행렬 거듭제곱을 통해 답을 구할 수 있으므로 상수 커팅의 효과가 있겠습니다.

 

제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 998244353

typedef struct {
	unsigned long long array[3][3];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, long long P);

Matrix Base =
{{
	{0, 1, 1},
	{1, 0, 0},
	{0, 1, 0}
}};

int main(void) {
	int T;
	scanf("%d", &T);
	while(T--) {
		long long N;
		scanf("%lld", &N);
		
		if (N <= 3) {
			printf("1\n");
			continue;
		}
		
		Matrix Answer = matrix_power_modular(Base, N - 3);
		printf("%llu\n", (Answer.array[0][0] + Answer.array[0][1] + Answer.array[0][2]) % mod);
	}
	return 0;
}

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

Matrix matrix_power_modular (Matrix A, long long P) {
	Matrix result = {{{}}};
	for (int i = 0; i < 3; i++) {
		result.array[i][i] = 1;
	}
	while(P) {
		if (P % 2) {
			result = matrix_multiply_modular (result, A);
		}
		A = matrix_multiply_modular (A, A);
		P /= 2;
	}
	return result;
}

(C11, 4ms, 1116KB, 제출번호 56631974)

---

단순한 코드인데, 0ms를 찍는 게 힘들어 포기했습니다.. 0ms을 기록하신 분의 코드는 읽어봤는데 아마 Padovan Sequence를 생성하는 matrix를 기반으로 한 것 같긴 합니다. 전반적인 알고리즘은 같은 듯한데, 0ms가 나온 건 함수의 inline화가 큰 영향이 있는 듯 하구요...

 

참고) 링크에 따르면, Fibonacci Sequence처럼 Padovan Sequence에서도 다음이 성립한다고 합니다.

$$\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}^{n} = \begin{bmatrix} P(n-5) & P(n-3) & P(n-4) \\ P(n-4) & P(n-2) & P(n-3) \\ P(n-3) & P(n-1) & P(n-2) \end{bmatrix}$$