백준 3827번: 일차원 세포 자동자

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

3827번: 일차원 세포 자동자

---

지문에서 설명하는 점화식을 그대로 행렬로 표현해주면 됩니다.

 

$S\left( i,t+1 \right)=A\times S\left( i-1,t \right)+B\times S\left( i,t \right)+C\times S\left( i+1,t \right)$

 

이 점화식에서 $i=0$ 일 때, $i=N-1$ 일 때만 잠시 생각해보면,

 

$S\left( 0,t+1 \right)=B\times S\left( 0,t \right)+C\times S\left( 1,t \right)$

 

$S\left( N-1,t+1 \right)=A\times S\left( N-2,t \right)+B\times S\left( N-1,t \right)$

 

위와 같은 식을 얻을 수 있습니다.

 

$T$ 의 범위가 매우 크기 때문에, $T$ 끼리의 상태 전이를 행렬로 표현해야 합니다.

 

그래서 다음 식을 얻습니다.

 

$\begin{bmatrix} S\left( 0,t+1 \right) \\ S\left( 1,t+1 \right) \\ S\left( 2,t+1 \right) \\ \vdots \\ S\left( N-3,t+1 \right) \\ S\left( N-2,t+1 \right) \\ S\left( N-1,t+1 \right) \end{bmatrix}=\begin{bmatrix} B & C & 0 & 0 & 0 & \cdots & 0 \\ A & B & C & 0 & 0 & \cdots & 0 \\ 0 & A & B & C & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & A & B & C & 0 \\ 0 & \cdots & 0 & 0 & A & B & C \\ 0 & \cdots & 0 & 0 & 0 & A & B \end{bmatrix} \begin{bmatrix} S\left( 0,t \right) \\ S\left( 1,t \right) \\ S\left( 2,t \right) \\ \vdots \\ S\left( N-3,t \right) \\ S\left( N-2,t \right) \\ S\left( N-1,t \right) \end{bmatrix}$

 

최종적인 식이 다음과 같습니다.

 

$\begin{bmatrix} S\left( 0,T \right) \\ S\left( 1,T \right) \\ S\left( 2,T \right) \\ \vdots \\ S\left( N-3,T \right) \\ S\left( N-2,T \right) \\ S\left( N-1,T \right) \end{bmatrix}=\begin{bmatrix} B & C & 0 & 0 & 0 & \cdots & 0 \\ A & B & C & 0 & 0 & \cdots & 0 \\ 0 & A & B & C & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & A & B & C & 0 \\ 0 & \cdots & 0 & 0 & A & B & C \\ 0 & \cdots & 0 & 0 & 0 & A & B \end{bmatrix}^{T} \begin{bmatrix} S\left( 0,0 \right) \\ S\left( 1,0 \right) \\ S\left( 2,0 \right) \\ \vdots \\ S\left( N-3,0 \right) \\ S\left( N-2,0 \right) \\ S\left( N-1,0 \right) \end{bmatrix}$

 

T는 transpose가 아니라 matrix의 exponentiation 입니다.

 

이를 구현하면 정답을 받을 수 있습니다. 제 코드는 다음과 같습니다.

#include <stdio.h>

typedef struct {
	int array[50][50];
} Matrix;

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

int main() {

	int N, M, A, B, C, T;
	
	while(1)
	{
		scanf("%d %d %d %d %d %d", &N, &M, &A, &B, &C, &T);
		if (N == 0 && M == 0 && A == 0 && B == 0 && C == 0 && T == 0) {
			break;
		}
		
		int power = T, size = N, mod = M;

		Matrix Answer = { {{0}} };
		for (int i = 0; i < size; i++) {
			scanf("%d", &Answer.array[i][0]);
		}
		
		Matrix Base = { {{0}} };
		Base.array[0][0] = B, Base.array[0][1] = C;
		Base.array[N-1][N-2] = A, Base.array[N-1][N-1] = B;
		for (int i = 1; i < size - 1; i++) {
			Base.array[i][i-1] = A;
			Base.array[i][i]   = B;
			Base.array[i][i+1] = C;
		}
	
		Base = matrix_power_modular (Base, power, size, mod);
		Answer = matrix_multiply_modular (Base, Answer, size, mod);
		
		for (int i = 0; i < size; i++) {
			printf("%d ", Answer.array[i][0]);
		}
		printf("\n");
	}

	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size, int mod) {
	Matrix result = { {{0}} };
	for (int i = 0; i < size; i++) {
		for (int k = 0; k < size; k++) {
			for (int j = 0; j < size; j++) {
				int 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, int mod) {
	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, A, size, mod);
		}
		A = matrix_multiply_modular (A, A, size, mod);
		power /= 2;
	}
	return result;
}

(C11, 1116KB, 824ms, 제출번호 31011510)

---

그런데, 시간이 지나치게 오래 걸렸습니다.

 

한 쿼리당 시간 복잡도가 $O\left( \;N^{3}\;logT\; \right)$ 인 건 다들 똑같을 텐데...

 

놀랍게도 행렬곱 함수를 다음과 같이 수정하자 시간이 크게 줄어들었습니다.

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

(C11, 1116KB, 452ms, 제출번호 31662558)

---

이후 다양한 변화를 줘가며 실행 시간을 관찰했는데, 다음과 같습니다.

 

$\left( 1 \right)$ matrix_multiply_modular 의 result 를 R 로 바꾸자 4ms 증가 (31662730) (456ms)

 

$\left( 2 \right)$ (1)에서 matrix_power_modular 의 result 도 R 로 바꾸자 다시 8ms 증가 (464ms) (31663295)

 

$\left( 3 \right)$ (1)에서 matrix_multiply_modular 을 k-i-j 순으로 바꾸자 28ms 증가 (484ms) (31662695)

 

$\left( 4 \right)$ (1)에서 matrix_multiply_modular 의 식을 변경하자 404ms 증가 (856ms) (31663050)

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

---