백준 25962번: 선우의 셋리스트

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

25962번: 선우의 셋리스트

---

 

잘 관찰하면 이 문제는 $1 \times N$ 크기의 직사각형을 $1 \times 1$부터 $1 \times 5$ 크기의 블록으로 타일링하는 경우의 수를 구하는 문제와 같다고 할 수 있습니다.

 

몇 가지 정의하겠습니다.

 

1분짜리, 2분짜리, 3분짜리, 4분짜리, 5분짜리 노래의 개수를 각각 $M_{1}$, $M_{2}$, $M_{3}$, $M_{4}$, $M_{5}$ 라고 하고,

$N$에 대한 셋리스트의 개수를 $A \left ( N \right )$라고 하겠습니다.

---

이제 작은 $N$에 대해 경우의 수를 구해보겠습니다.

 

$$ A \left ( 1 \right ) = M_{1} $$

$$ A \left ( 2 \right ) = M_{1} A \left ( 1 \right ) + M_{2} $$

$$ A \left ( 3 \right ) = M_{1} A \left ( 2 \right ) + M_{2} A \left ( 1 \right ) + M_{3} $$

$$ A \left ( 4 \right ) = M_{1} A \left ( 3 \right ) + M_{2} A \left ( 2 \right ) + M_{3} A \left ( 1 \right ) + M_{4} $$

$$ A \left ( 5 \right ) = M_{1} A \left ( 4 \right ) + M_{2} A \left ( 3 \right ) + M_{3} A \left ( 2 \right ) + M_{4} A \left ( 1 \right ) + M_{5} $$

 

그리고 $N > 5$에 대해 다음이 성립함을 쉽게 알 수 있습니다.

 

$$ A \left ( N \right ) = M_{1} A \left ( N-1 \right ) + M_{2} A \left ( N-2 \right ) + M_{3} A \left ( N-3 \right ) + M_{4} A \left ( N-4 \right ) + M_{5} A \left ( N-5 \right ) $$

 

아직까지는 복잡도가 $O \left ( N \right )$ 이므로, 행렬 거듭제곱을 활용하여 복잡도를 $O \left ( \log N \right )$ 으로 떨어뜨립니다.

 

$$ \begin{bmatrix} A \left ( N \right ) \\ A \left ( N-1 \right ) \\ A \left ( N-2 \right ) \\ A \left ( N-3 \right ) \\ A \left ( N-4 \right ) \end{bmatrix} = \begin{bmatrix} M_{1} & M_{2} & M_{3} & M_{4} & M_{5} \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} A \left ( N-1 \right ) \\ A \left ( N-2 \right ) \\ A \left ( N-3 \right ) \\ A \left ( N-4 \right ) \\ A \left ( N-5 \right ) \end{bmatrix} $$

$$ = \begin{bmatrix} M_{1} & M_{2} & M_{3} & M_{4} & M_{5} \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix}^{N-5} \begin{bmatrix} A \left ( 5 \right ) \\ A \left ( 4 \right ) \\ A \left ( 3 \right ) \\ A \left ( 2 \right ) \\ A \left ( 1 \right ) \end{bmatrix} $$

 

아래는 이 풀이를 구현한 제 코드입니다.

#include <stdio.h>
#define mod 1000000007

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

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

int main() {
	
	long long N, M;
	scanf("%lld %lld", &N, &M);

	long long count[6] = {};
	while(M--)
	{
		int temp;
		scanf("%d", &temp);
		count[temp]++;
	}
	
	long long simple[6] = {};
	for (int i = 1; i <= 5; i++) {
		simple[i] = count[i] % mod;
		for (int j = 1; j < i; j++) {
			simple[i] = (simple[i] + count[j] * simple[i - j]) % mod;
		}
	}
	
	if (N <= 5) {
		printf("%lld", simple[N]);
		return 0;
	}
	
	Matrix Base = {{{}}};
	for (int i = 0; i < 5; i++) {
		Base.array[0][i] = count[i + 1];
	}
	for (int i = 1; i < 5; i++) {
		Base.array[i][i-1] = 1;
	}
	Base = matrix_power_modular(Base, N - 5);
	
	long long Answer = 0;
	for (int i = 0; i < 5; i++) {
		Answer = (Answer + Base.array[0][i] * simple[5 - i]) % mod;
	}
	printf("%lld", Answer);
	
	return 0;
}

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

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

(C11, 12ms, 1116KB, 제출번호 53526414)

---

인풋의 크기가 큰 편이므로 Fast I/O를 활용하여 속도를 높일 수 있습니다. (0ms, 제출번호 53526774)