백준 23819번: 묻고 더블로 마셔

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

23819번: 묻고 더블로 마셔

 

---

 

2021 POSTECH Programming Contest 의 G 번 문제라고 합니다.

 

다만, 이 블로그에서 익히 다뤄온 유형의 문제임을 쉽게 알 수 있습니다.

2021.02.19 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 17272번: 리그 오브 레전설 (Large)

2021.02.19 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 16467번: 병아리의 변신은 무죄

 

그러므로 설명은 다소 생략하고, 점화식을 소개하겠습니다.

 

$$\begin{bmatrix} a_{n} \\ a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{n-k+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 0 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{n-k} \end{bmatrix}$$

 

$$\leftrightarrow \begin{bmatrix} a_{n} \\ a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{n-k+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 0 \end{bmatrix} ^{n-k} \begin{bmatrix} a_{k} \\ a_{k-1} \\ a_{k-2} \\ \vdots \\ a_{1} \end{bmatrix}$$

 

이대로 구현하면 끝입니다.

 

제 코드는 다음과 같습니다.

 

/*
 * Author : thdtjdals3
 * Date : 2021-12-17
 * Description : BOJ 23819
 * Link : https://www.acmicpc.net/problem/23819
 */

#include <stdio.h>

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

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size, int M);
Matrix matrix_power_modular (Matrix A, int P, int size, int M);

int main() {
	
	int n, K;
	scanf("%d %d", &n, &K);
	
	Matrix Base = { {{0}} };
	for (int i = 0; i < K; i++)
	{
		Base.array[0][i] = 1;
	}
	for (int i = 0; i < K - 1; i++)
	{
		Base.array[i + 1][i] = 1;
	}
	
	unsigned long long int v[100] = {0};
	for (int i = 0; i < K; i++)
	{
		scanf("%llu", &v[K - 1 - i]);
	}

	int P;
	scanf("%d", &P);
	
	Base = matrix_power_modular (Base, n - K, K, P);
	unsigned long long answer = 0;
    for (int i = 0; i < K; i++)
    {
        answer = (answer + v[i] * Base.array[0][i]) % P;
    }
    
    printf("%llu", answer);
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size, int M)
{
	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]) % M;
			}
		}
	}
	return result;
}

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

(C11, 424ms, 1620KB, 제출번호 36400941)

---

 

이 문제는 Kitamasa 또는 Berlekamp-Massey 같은 알고리즘으로도 잘 풀리는 듯합니다.

 

앞서 소개한 두 문제보다 시간이 특히 오래 걸리는데, 아무래도 modulo 의 값이 변수로 주어지는 게 문제 같네요.

 

한 번 Berlekamp Massey 로도 풀어보고 싶습니다.