백준 13630번: Buses

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

13630번: Buses

---

 

문제를 잘 읽으면 결국 $1 \times N$ 직사각형을 $1 \times 5$, $1 \times 10$ 블록으로 타일링하는 방법의 수를 구하는 게 끝입니다.

$N$이 5의 배수임이 보장되므로 타일링하는 경우의 수가 $f \left ( N \right )$라고 정의한다면 다음이 성립합니다.

 

$$ f \left ( N \right ) = K f \left ( N-5 \right ) + L f \left ( N-10 \right ) $$

 

복잡도가 $O \left ( N \right )$이므로 점화식을 행렬 형태로 바꾸고 binary exponentiation을 활용하여 $O \left ( \log N \right )$ 으로 낮춥니다.

$N \geq 10$에 대해,

$$ \begin{bmatrix} f \left ( N+10 \right ) \\ f \left ( N+5 \right ) \\ f \left ( N \right ) \end{bmatrix} = \begin{bmatrix} K & L & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} f \left ( N+5 \right ) \\ f \left ( N \right ) \\ f \left ( N-5 \right ) \end{bmatrix} $$

식을 보다 간소화하기 위해, $f \left ( 0 \right ) = 1$로 정의합니다. 그러면 $N \geq 15$에 대해 아래가 성립합니다.

$$ \begin{bmatrix} f \left ( N \right ) \\ f \left ( N-5 \right ) \\ f \left ( N-10 \right ) \end{bmatrix} = \begin{bmatrix} K & L & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}^{\frac{N}{5} - 2} \begin{bmatrix} f \left ( 10 \right ) \\ f \left ( 5 \right ) \\ f \left ( 0 \right ) \end{bmatrix} $$

자명하게 $f \left ( 5 \right ) = K$이고, $f \left ( 10 \right ) = K^{2} + L$ 입니다.

 

그러므로 최종 식은 아래와 같습니다.

$$ \begin{bmatrix} f \left ( N \right ) \\ f \left ( N-5 \right ) \\ f \left ( N-10 \right ) \end{bmatrix} = \begin{bmatrix} K & L & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}^{\frac{N}{5} - 2} \begin{bmatrix} K^{2}+L \\ K \\ 1 \end{bmatrix} $$

 

문제의 출력 조건, $K$와 $L$의 범위에 주의하여 구현하면 해결됩니다. 다음은 제 코드입니다.

#include <stdio.h>
#define mod 1000000

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

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



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

    K %= mod;
    L %= mod;
    
	long long simple[4] = {0, 1, K, (K * K + L) % mod};
	if (N <= 10)
	{
		printf("%06lld", simple[N/5 + 1]);
		return 0;
	}

	Matrix Base =
	{{
		{ K, L, 0 },
		{ 1, 0, 0 },
		{ 0, 1, 0 }
	}};
	Base = matrix_power_modular(Base, N / 5 - 2);

	long long answer = 0;
	for (int i = 0; i < 3; i++)
	{
		answer = (answer + Base.array[0][i] * simple[3 - i]) % mod;
	}
	printf("%06lld", answer);
	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 > 0)
	{
		if (P % 2)
		{
			result = matrix_multiply_modular (result, A);
		}
		A = matrix_multiply_modular (A, A);
		P /= 2;
	}
	return result;
}

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

---