백준 16467번: 병아리의 변신은 무죄

www.acmicpc.net/problem/16467

16467번: 병아리의 변신은 무죄

---

이전에 올렸던 (백준 17272번: 리그 오브 레전설 (Large))과 상당히 비슷한 문제라고 할 수 있습니다.

 

주어진 힌트를 잘 분석하면, $i$ 번째 날에 처음 등장한 알은 $i+K$ 번째 날에 병아리가 된다는 걸 알 수 있습니다.

 

$i$ 번째 날의 병아리의 수를 $A_{i}$ 라고 표기하겠습니다.

 

$i$ 번째 날에 처음 등장한 알은 곧 $i-1$ 번째 날의 병아리들이 낳은 알이므로 그 개수가 $A_{i-1}$ 이 될 것입니다.

 

따라서, $A_{i-1}$ 개의 알이 $\left ( i-1 \right )+\left ( K+1 \right )$ 번째 날에 병아리가 됩니다.

 

즉 $N\geq K+1$인 $N$에 대해 $A_{N}=A_{N-1}+A_{N-\left ( K+1 \right )}$이 성립한다고 할 수 있습니다.

 

이제 17272번과 비슷한 방법으로 행렬 형태의 점화식을 유도하면 끝일 것 같습니다.

 

 

$\begin{bmatrix}A_{N-\left(K+1 \right)}\\ A_{N-K}\\ A_{N-\left(K-1 \right)}\\ \vdots\\ A_{N-2}\\ A_{N-1} \\ A_{N}\end{bmatrix}=\begin{bmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0\\ 0 & 0 & 1 & 0 & \cdots & 0 & 0\\ 0 & 0 & 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & 1 & 0\\ 0 & 0 & 0 & 0 & \cdots & 0 & 1\\ 0 & 1 & 0 & 0 & \cdots & 0 & 1\end{bmatrix}\begin{bmatrix}A_{N-1-\left(K+1 \right)}\\ A_{N-1-K}\\ A_{N-1-\left(K-1 \right)}\\ \vdots\\ A_{N-1-2}\\ A_{N-1-1}\\ A_{N-1}\end{bmatrix}$

 

정말 끝일까요?

 

이 행렬 점화식이 성립하는 $N$의 범위가 $N\geq K+1$ 임은 이미 아실 것입니다.

 

그러면 저 점화식이 성립하는 $K$의 범위는 어떻게 될까요?

 

$K=0$일 때는 왠지 성립하지 않을 것 같다는 직감이 듭니다.

 

그런데 사실 $K=0$일 때는

 

$A_{N}=A_{N-1}+A_{N-\left ( K+1 \right )}=2\times A_{N-1}$ 이고,

 

$A_{0}=1$이라고 문제에서 주어졌으므로,

 

$A_{N}=2^{N}$

 

임을 쉽게 알 수 있습니다.

 

그러면 $K=1$일 때는 어떨까요?

 

$K=1$일 때 $A_{N}=A_{N-1}+A_{N-2}$ 이고,

 

$\begin{bmatrix}A_{N-2}\\ A_{N-1}\\ A_{N}\end{bmatrix}=\begin{bmatrix}0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 1 & 1\end{bmatrix}\begin{bmatrix}A_{N-3}\\ A_{N-2}\\ A_{N-1}\end{bmatrix}$

 

이므로 행렬 점화식이 성립함을 쉽게 알 수 있습니다.

 

이제 일반적으로 쉽게 구할 수 있는 $N\leq K+2$ 일 때의 값들만 추가적으로 예외처리 해주면 되겠습니다.

 

$1\leq i\leq K$인 $i$ 에 대해 $A_{i}=1$ 입니다.

 

또 이때 $A_{K+1}=2$ 이고, $A_{K+2}=3$ 입니다.

 

최종적으로 테스트케이스 하나 당 시간복잡도는

 

$K$ 가 자연수일 때 $O\left ( K^{3}logN \right )$,   $K=0$일 때 $O\left( logN \right)$이 될 것입니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#define mod 100000007

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

long long power_modular (long long x, long long y);

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

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		int K, N;
		scanf("%d %d", &K, &N);
		
		if (K == 0) {
			printf("%lld\n", power_modular(2, N));
			continue;
		}
		
		if (N <= K) {
			printf("1\n");
			continue;
		}
		if (N == K + 1) {
			printf("2\n");
			continue;
		}
		if (N == K + 2) {
			printf("3\n");
			continue;
		}
		
		int size = K + 2, power = N - K - 2;
		
		Matrix Base = { {0,} };
		for (int i = 0; i < size - 1; i++) {
			Base.array[i][i+1] = 1;
		}
		Base.array[size-1][1] = Base.array[size-1][size-1] = 1;
		
		Matrix Answer = { {0,} };
		for (int i = 0; i < size - 2; i++) {
			Answer.array[i][0] = 1;
		}
		Answer.array[size-2][0] = 2, Answer.array[size-1][0] = 3;
		
		Base = matrix_power_modular (Base, size, power);
		Answer = matrix_multiply_modular (Base, Answer, size);
		
		printf("%lld\n", Answer.array[size-1][0]);
	}
	return 0;
}

long long power_modular (long long x, long long y) {
	x %= mod;
	long long result = 1;
	while(y) {
		if (y % 2) {
			result = (result * x) % mod;
		}
		x = (x * x) % mod;
		y /= 2;
	}
	return result;
}

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

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

 

(C11, 1116KB, 8ms, 제출번호 26480166)

---

처음엔 power을 $N-K-1$로 두는 방안을 시도해봤는데, 이유는 잘 모르겠으나 WA를 받아서

 

power을 $N-K-2$로 두고 풀었습니다.

 

자연수 $K$ 에 대해 $A_{K+1}$ 의 값은 2인데,

 

0일에 있던 병아리 1마리가 낳은 알 1개가 $K+1$ 일에 병아리가 되기 때문입니다.

 

또 $A_{K+2}$ 의 값은 3이라고 했는데,

 

자연수 $K$ 에 대해 $A_{1}$ 의 값이 항상 1이므로

 

1일에 있던 병아리 1마리가 낳은 알 1개가 $K+2$ 일에 병아리가 되기 때문입니다.

 

---

locality를 고려한 코드 수정이 있었습니다. (2021/4/4)

 

#include <stdio.h>
#define mod 100000007

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

long long power_modular (long long x, long long y);

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

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		int K, N;
		scanf("%d %d", &K, &N);
		
		if (K == 0) {
			printf("%lld\n", power_modular(2, N));
			continue;
		}
		
		if (N <= K) {
			printf("1\n");
			continue;
		}
		if (N == K + 1) {
			printf("2\n");
			continue;
		}
		if (N == K + 2) {
			printf("3\n");
			continue;
		}
		
		int size = K + 2, power = N - K - 2;
		
		Matrix Base = { {{0}} };
		for (int i = 0; i < size - 1; i++) {
			Base.array[i][i+1] = 1;
		}
		Base.array[size-1][1] = Base.array[size-1][size-1] = 1;
		
		Matrix Answer = { {{0}} };
		for (int i = 0; i < size - 2; i++) {
			Answer.array[i][0] = 1;
		}
		Answer.array[size-2][0] = 2, Answer.array[size-1][0] = 3;
		
		Base = matrix_power_modular (Base, size, power);
		Answer = matrix_multiply_modular (Base, Answer, size);
		
		printf("%lld\n", Answer.array[size-1][0]);
	}
	return 0;
}

long long power_modular (long long x, long long y) {
	x %= mod;
	long long result = 1;
	while(y) {
		if (y % 2) {
			result = result * x % mod;
		}
		x = x * x % mod;
		y /= 2;
	}
	return result;
}

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

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

 

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

---