백준 9341번: ZZ

www.acmicpc.net/problem/9341

9341번: ZZ

---

이전 글 (백준 13430번: 합 구하기) 을 보고 오셨다면 비슷한 점을 느끼실 수 있는 문제입니다.

 

사실 풀이가 거의 똑같습니다.

 

그런 점에서 이 문제는 처음부터 식 변형을 통해 점화식을 이끌어내겠습니다.

 

우선 $i\geq 1$에 대해 $ZZ\left(i,1 \right)=a$ 입니다.

 

이는 다음을 통해 보일 수 있습니다.

 

$ZZ\left(i,1 \right)=ZZ\left(i-1,1 \right)=\cdots=ZZ\left(1,1 \right)=ZZ\left(0,1 \right)=a$

 

이제 다음 두 식을 비교해보겠습니다.

 

$ZZ\left(i,k \right)=ZZ\left(i-1,k \right)+ZZ\left(i-1,k-1 \right)+\cdots+ZZ\left(i-1,2 \right)+ZZ\left(i-1,1 \right)$

$ZZ\left(i,k-1 \right)=ZZ\left(i-1,k-1 \right)+ZZ\left(i-1,k-2 \right)+\cdots+ZZ\left(i-1,2 \right)+ZZ\left(i-1,1 \right)$

 

따라서, 다음이 성립합니다.

 

$ZZ\left(i,k \right)=ZZ\left(i-1,k \right)+ZZ\left(i,k-1 \right)$

 

이제 다음과 같이 식을 계속 변형합니다.

 

$ZZ\left(i,j \right)=ZZ\left(i,j-1 \right)+ZZ\left(i-1,j \right)$

$ZZ\left(i,j \right)=ZZ\left(i,j-1 \right)+ZZ\left(i-1,j-1 \right)+ZZ\left(i-2,j \right)$

$ZZ\left(i,j \right)=ZZ\left(i,j-1 \right)+ZZ\left(i-1,j-1 \right)+ZZ\left(i-2,j-1 \right)+ZZ\left(i-3,j \right)$

$\vdots$

$ZZ\left(i,j \right)=ZZ\left(i,j-1 \right)+ZZ\left(i-1,j-1 \right)+\cdots+ZZ\left(2,j-1 \right)+ZZ\left(1,j \right)$

$ZZ\left(i,j \right)=ZZ\left(i,j-1 \right)+ZZ\left(i-1,j-1 \right)+\cdots+ZZ\left(2,j-1 \right)+ZZ\left(1,j-1 \right)+ZZ\left(0,j \right)$

 

최종적으로 다음을 얻습니다.

 

$ZZ\left(i,j \right)=ZZ\left(i,j-1 \right)+ZZ\left(i-1,j-1 \right)+\cdots+ZZ\left(1,j-1 \right)+ZZ\left(0,j-1 \right)+ZZ\left(0,j-2 \right)$

 

이제 이 식을 행렬 점화식으로 바꿔주겠습니다.

 

$\begin{bmatrix}ZZ\left(0,j-1 \right)\\ ZZ\left(0,j \right)\\ ZZ\left(1,j \right)\\ ZZ\left(2,j \right)\\ \vdots\\ ZZ\left(i-1,j \right)\\ ZZ\left(i,j \right)\end{bmatrix}=\begin{bmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & 1 & \cdots & 1 & 0\\ 1 & 1 & 1 & 1 & \cdots & 1 & 1\end{bmatrix}\begin{bmatrix}ZZ\left(0,j-2 \right)\\ ZZ\left(0,j-1 \right)\\ ZZ\left(1,j-1 \right)\\ ZZ\left(2,j-1 \right)\\ \vdots\\ ZZ\left(i-1,j-1 \right)\\ ZZ\left(i,j-1 \right)\end{bmatrix}$

 

 

결과적으로 각 테스트 케이스는 다음과 같이 구할 수 있습니다.

 

$\begin{bmatrix}ZZ\left(0,d-1 \right)\\ ZZ\left(0,d \right)\\ ZZ\left(1,d \right)\\ ZZ\left(2,d \right)\\ \vdots\\ ZZ\left(c-1,d \right)\\ ZZ\left(c,d \right)\end{bmatrix}=\begin{bmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & 1 & \cdots & 1 & 0\\ 1 & 1 & 1 & 1 & \cdots & 1 & 1\end{bmatrix}^{d-2}\begin{bmatrix}ZZ\left(0,1 \right)\\ ZZ\left(0,2 \right)\\ ZZ\left(1,2 \right)\\ ZZ\left(2,2 \right)\\ \vdots\\ ZZ\left(c-1,2 \right)\\ ZZ\left(c,2 \right)\end{bmatrix}$

 

그런데, $ZZ\left(c,2 \right)$ 의 값을 우리가 쉽게 구할 수 있을까요?

 

만약 쉽게 구할 수 없다면 다음과 같은 식은 어떨까요?

 

$\begin{bmatrix}ZZ\left(0,d-1 \right)\\ ZZ\left(0,d \right)\\ ZZ\left(1,d \right)\\ ZZ\left(2,d \right)\\ \vdots\\ ZZ\left(c-1,d \right)\\ ZZ\left(c,d \right)\end{bmatrix}=\begin{bmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 0 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & 0 & \cdots & 0 & 0\\ 1 & 1 & 1 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & 1 & \cdots & 1 & 0\\ 1 & 1 & 1 & 1 & \cdots & 1 & 1\end{bmatrix}^{d-1}\begin{bmatrix}ZZ\left(0,0 \right)\\ ZZ\left(0,1 \right)\\ ZZ\left(1,1 \right)\\ ZZ\left(2,1 \right)\\ \vdots\\ ZZ\left(c-1,1 \right)\\ ZZ\left(c,1 \right)\end{bmatrix}$

 

우리는 $ZZ\left(c,1 \right)$은 $a$라고 알고 있는데

 

$ZZ\left(0,0 \right)$이 문제입니다.

 

주어진 식 $ZZ\left(0,k \right)=ZZ\left(0,k-1 \right)+ZZ\left(0,k-2 \right)$가 $k=2$일 때도 성립하면 참 좋을텐데요.

 

$k\geq 2$까지 주어진 식을 확장해도 모순이 없는지 확인해볼 필요가 있습니다.

 

그런데 당연하게도 모순이 없습니다. ZZ 함수의 정의에는

 

ZZ 함수의 치역은 0 이상의 정수이다

 

이런 제한이 전혀 없거든요.

 

그러므로 $ZZ\left(0,0 \right)=ZZ\left(0,2 \right)-ZZ\left(0,1 \right)=b-a$ 라고 할 수 있습니다.

 

이제 음수 모듈러 연산에 주의하여 구현만 하면 끝입니다.

 

최종적으로 시간복잡도 $O\left(T\times C^{3}logD \right)$ 이 되겠습니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#define mod 1000000009

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

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

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		
		long long a, b;
		int c, d;
		scanf("%lld %lld %d %d", &a, &b, &c, &d);
		
		if (d == 1) {
			printf("%lld\n", a);
			continue;
		}
		
		int size = c + 2;
		
		Matrix Base;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (j <= i) {
					Base.array[i][j] = 1;
				}
				else {
					Base.array[i][j] = 0;
				}
			}
		}
		Base.array[0][0] = 0, Base.array[0][1] = 1;
		
		long long temp = b - a;
		while(temp < 0) {
			temp += mod;
		}
		
		Matrix Answer;
		for (int i = 0; i < size; i++) {
			if (i == 0) {
				Answer.array[i][0] = temp;
			}
			else {
				Answer.array[i][0] = a;
			}
			for (int j = 1; j < size; j++) {
				Answer.array[i][j] = 0;
			}
		}
		
		Base = matrix_power_modular(Base, d - 1, size);
		Answer = matrix_multiply_modular(Base, Answer, size);
		
		printf("%llu\n", Answer.array[c+1][0]);
	}
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
	Matrix result;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			result.array[i][j] = 0;
			for (int k = 0; k < size; k++) {
				unsigned 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 A, int power, int size) {
	Matrix result;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			if (i == j) {
				result.array[i][j] = 1;
			}
			else {
				result.array[i][j] = 0;
			}
		}
	}
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular(result, A, size);
		}
		A = matrix_multiply_modular(A, A, size);
		power /= 2;
	}
	return result;
}

 

(C11, 1724KB, 5288ms, 제출번호 26364485)

---

다른 분들의 풀이를 봤을 때 0ms까지 줄어들 수 있다는 게 정말 믿기지가 않는 문제였습니다.

 

한편 matrix Answer을 굳이 사용하지 않고 for문으로 더 빠르게 답을 구할 수 있습니다.

 

전문 중에 수정된 일부만 가져오자면 다음과 같습니다.

 

Base = matrix_power_modular(Base, d - 1, size);
		
long long temp = b - a;
while(temp < 0) {
	temp += mod;
}
		
unsigned long long answer = (Base.array[c+1][0] * temp) % mod;
		
for (int i = 1; i < size; i++) {
	answer = (answer + (Base.array[c+1][i] * a) % mod) % mod;
}

 

(C11, 1644KB, 5092ms, 제출번호 26365360)

 

locality 개념을 이용하여 다음과 같이 코드 수행 시간을 더욱 줄일 수 있었습니다.

 

수정된 일부만 가져왔습니다.

 

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++) {
				unsigned long long temp = (A.array[i][k] * B.array[k][j]) % mod;
				result.array[i][j] = (result.array[i][j] + temp) % mod;
			}
		}
	}
	return result;
}

(C11, 1640KB, 3292ms, 제출번호 28021177)

---

제가 제출한 코드 중에는 unsigned long long을 long long으로 교체한 코드도 있었는데,

 

그 경우 6504ms가 걸리기도 했습니다.(제출번호 26364928)

 

이유를 알 수 없네요...