[ICPC][BOJ] 13328 - Message Passing

문제 : https://www.acmicpc.net/problem/13328

---

[알고리즘풀이]

최대 call 횟수 d 와 시간 t 초가 주어졌을 때,

F(N) : Number of calls at time N ( N초에서 호출 횟수) 라고 정의하자.

그러면, 다음과 같은 점화식이 성립한다.

피보나치의 변형꼴로 F(t)를 구하기 위해서는 위의 점화식을 이용해야 한다.

점화식을 구하는 것도 어려웠는데, t 가 최대 20억까지 입력이 들어오므로, 단순히 반복문을 통해 F(t) 를 구하면 안 된다.

따라서, 행렬을 이용해서 F(t) 를 구해야 한다.

위의 점화식을 이용해 다음과 같은 행렬 곱셈이 성립함을 알아낼 수 있다.

이 연산을 반복하면 다음과 같은 행렬식을 얻어낼 수 있다.

즉, 행렬 A의 ( t - d ) 제곱을 구하면, F(t) 를 구할 수 있다.

이때, 행렬 A의 ( t - d ) 제곱은 메모리제이션을 이용해

다음과 같이 A의 2^n 승을 구해놓고, A의 2^n 승을 이용해 A의 ( t - d ) 제곱을 구할 수 있다.

#include<iostream>
#include<cmath>

using namespace std;

#define mod 31991
int d, t, list[51];

int map[33][50][50];
int answer[50][50];
int tanswer[50][50];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> d >> t;
	for (int i = 1; i <= d; i++)
		list[i] = (long long)pow(2, i - 1) % mod;
	if (t <= d){
		cout << list[t];
		return 0;
	}
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < d; j++) {
			if (i == 0)
				map[0][i][j] = 1;
			else if (i == j + 1)
				map[0][i][j] = 1;
		}
	}

	int b = t - d;
	for (int i = 0; i < d; i++)
		for (int j = 0; j < d; j++)
			if (i == j)
				answer[i][j] = 1;
	int l;
	for (l = 0; ; l++)
		if ((long long)(pow(2, l)) > b)
			break;
	l--;
	for (int i = 1; i <= l; i++) {
		for (int j = 0; j < d; j++) {
			for (int k = 0; k < d; k++) {
				int temp = 0;
				for (int m = 0; m < d; m++) {
					temp += (map[i - 1][j][m] * map[i - 1][m][k]) % mod;
				}
				map[i][j][k] = temp % mod;
			}
		}
	}
	while (b) {
		int l;
		for (l = 0; ; l++) {
			if ((long long)(pow(2, l)) > b)
				break;
		}
		l--;
		for (int i = 0; i < d; i++) {
			for (int j = 0; j < d; j++) {
				int temp = 0;
				for (int m = 0; m < d; m++) {
					temp += (answer[i][m] * map[l][m][j]) % mod;
				}
				tanswer[i][j] = temp % mod;
			}
		}
		for (int i = 0; i < d; i++)
			for (int j = 0; j < d; j++)
				answer[i][j] = tanswer[i][j];
		b -= (long long)pow(2, l);

	}
	int k = 0;
	for (int i = 1; i <= d; i++) {
		k += (answer[0][i - 1] * list[d + 1 - i]) % mod;
		k = k % mod;
	}
	cout << k % mod;
}

---

푸는데 정말 애먹은 문제로, 점화식을 끌어내는 과정 + 점화식을 이용해 행렬 계산을 하는 과정까지

전부 다 어려웠던 문제입니다.