백준 24930번: Ordinary Ordinals

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

24930번: Ordinary Ordinals

---

폰 노이만이 자연수를 정의한 것을 차용한 문제입니다.

$N$에 대응되는 괄호 문자열의 길이를 $a_{N}$라고 하면, $N \geq 1$에 대해 다음이 성립함을 알 수 있습니다.

 

$$ a_{N} = a_{0} + a_{1} + a_{2} + \cdots + a_{N-1} + 2 + N-1 $$

 

위 식에서 $2$ 는 가장 바깥쪽의 괄호쌍, $N-1$ 은 콤마의 개수입니다.

 

이를 그대로 구현할 경우 $O \left ( N^{2} \right )$이라서, 약간의 식 변형을 통해 좀 더 간소한 점화식을 얻어보겠습니다.

 

$$ a_{N+1} = a_{0} + a_{1} + a_{2} + \cdots + a_{N-1} + a_{N} + 2 + N $$

$$ \therefore a_{N+1} - a_{N} = a_{N} + 1 \rightarrow a_{N+1} = 2a_{N} + 1$$

 

위 식은 $N \geq 1$에서 성립하고, 문제에서 주어진 대로 $a_{0}=2$ , $a_{1}=4$ 입니다.

이제 복잡도는 $O \left ( N \right )$으로 줄었지만, 여기서 복잡도를 $O \left ( \log N \right )$으로 줄이는 방법이 2가지 있습니다.

---

첫번째 방법은 일반항을 구하는 것입니다.

 

수열 $\left \{ b_{n} \right \} = a_{n} + 1$ 을 도입하여 다음을 알 수 있습니다.

 

$$ b_{N+1} = 2b_{N} $$

 

정의에 따라 $b_{1}=5$ 이므로, 수열의 일반항 $b_{N}=5 \times 2^{N-1}$ 을 얻습니다. ($N \geq 1$)

 

결과적으로 $a_{N} = 5 \times 2^{N-1} - 1$ 입니다. ($N \geq 1$)

---

두번째 방법은 행렬 점화식을 구하는 것입니다.

위에서 얻은 식을 그대로 활용하여 다음을 얻을 수 있습니다.

 

$$ \begin{bmatrix} a_{N+1} \\ a_{N} \\ 1 \end{bmatrix} = \begin{bmatrix} 2 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{N} \\ a_{N-1} \\ 1 \end{bmatrix} $$

위 식은 $N \geq 1$에 대해 성립합니다. 즉, $N \geq 2$에 대해 다음이 성립합니다.

$$ \begin{bmatrix} a_{N} \\ a_{N-1} \\ 1 \end{bmatrix} = \begin{bmatrix} 2 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^{N-1} \begin{bmatrix} a_{1} \\ a_{0} \\ 1 \end{bmatrix} = \begin{bmatrix} 2 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^{N-1} \begin{bmatrix} 4 \\ 2 \\ 1 \end{bmatrix} $$

---

둘 다 올바른 방법이므로 어느쪽을 쓰든 상관 없지만, 만약 제한 시간이 더 짧아지거나, $M$이 더욱 커진다면 저는 첫번째 방법을 썼을 것 같습니다.

 

$M$이 $10^{18}$ scale로 커진다면 C 특성상 로그 시간 곱셈까지 동원하게 됩니다.

이 경우 곱셈 횟수가 행렬 곱셈을 활용하는 두 번째 방법이 월등히 크기 때문에, 실행 시간 차이가 커질 거라는 게 제 생각입니다.

 

그러나 $M < 2^{31}$ 이므로, $2^{63}$ scale의 $N$으로는 두 방법의 실행 시간 차이가 크진 않을 것 같습니다.

 

아래는 두 번째 방법으로 구현한 제 코드입니다.

#include <stdio.h>

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

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

long long simple[4] = {0, 1, 2, 4};

int main() {
	
	long long N, M;
	scanf("%lld %lld", &N, &M);
    
    if (N == 0)
    {
        printf("%d", 2 % M);
        return 0;
    }
    else if (N == 1)
    {
        printf("%d", 4 % M);
        return 0;
    }

	Matrix Base =
	{{
		{ 2, 0, 1 },
		{ 1, 0, 0 },
		{ 0, 0, 1 }
	}};
	Base = matrix_power_modular(Base, N - 1, M);

	long long answer = 0;
	for (int i = 0; i < 3; i++)
	{
		answer = (answer + Base.array[0][i] * simple[3 - i]) % M;
	}
	printf("%lld", answer);
	return 0;
}

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

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

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

---

위 수열은 OEIS에 등재되어 있습니다. http://oeis.org/A153894