백준 14559번: Protocol

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

14559번: Protocol

---

이 문제는 정말 의외로, 그래프 이론에 관한 문제입니다.

 

우선 용량이 $i$ 인 전선의 가치가 $112345^{i}$ 라고 주어져 있습니다.

 

그래서 $X$ 를 기준으로 $f\left( X \right) \; , \; g\left( X \right) \; , \; f\left( g\left( X \right) \right) \; , \cdots$ 를 다 구하려다가는, 절대 풀 수 없습니다.

 

그런데 우리가 modulo $\left( 10^{9}+9 \right)$ 를 구해야하는 상황이라면 조금 얘기가 다르죠.

 

다음 사실을 알 수 있습니다.

 

$112345^{167}=1 \;\; mod \;\; \left( 10^{9}+9 \right)$

 

이에 따르면 사실 우리가 구해야 하는 것은 $X \; , \; f\left( X \right) \; , \; g\left( X \right) \; , \; f\left( g\left( X \right) \right) \; , \cdots$ 의 modulo 167 입니다!

 

여전히 하나하나 탐색하고 있으면 $2^{M}$ 인데요...

 

여기서 그래프 이론을 사용합니다. 아이디어는 다음과 같습니다.

 

$167\times 167$ 행렬을 구성하여, 그 entries를 다음과 같이 구성합니다.

 

$\left[ 0 \right] \left[ f\left( 0 \right)\;mod\;167 \right]$ 에 $+1$ ,

$\left[ 0 \right] \left[ g\left( 0 \right)\;mod\;167 \right]$ 에 $+1$ ,

$\left[ 1 \right] \left[ f\left( 1 \right)\;mod\;167 \right]$ 에 $+1$ ,

$\left[ 1 \right] \left[ g\left( 1 \right)\;mod\;167 \right]$ 에 $+1$

$\vdots$

 

이렇게 구성한 행렬은, 초기 용량에서 1년 후의 용량으로의 경로가 됩니다!

 

이 행렬을 일종의 인접행렬로 인식한다면

 

$M=2$ 일 때도, $M=10^{9}$ 일 때도 그저 위 행렬을 $M$ 제곱하면 끝입니다. 그렇죠?

 

답은 어떻게 구할까요?

 

우리가 원하는 것은 시작 용량이 $N$ 인 경우 뿐이니까 $N^{th}$ row 의 모든 entry를 살피면 됩니다.

 

이때 각 $\left[ N \right] \left[ i \right]$는 $N$ 에서 출발하여 $i$ 로 도착하는 방법의 수겠죠.

 

그래서, 그 용량에 해당하는 가치 $112345^{i}$ 를 곱해주면 됩니다.

 

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

#include <stdio.h>
#define mod 1000000009

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

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, int Power);

long long power_modular (long long A, int Power);

int main() {
	
	int N, M;
	scanf("%d %d", &N, &M);
	
	long long a, b, c, d, e, f;
	scanf("%lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &e, &f);
	
	Matrix Base = { {{0}} };
	for (int i = 0; i < 167; i++) {
		Base.array[i][(a*i*i + b*i + c) % 167] += 1;
		Base.array[i][(d*i*i + e*i + f) % 167] += 1;
	}
	
	N %= 167;
	Base = matrix_power_modular(Base, M);
	
	long long Answer = 0;
	for (int i = 0; i < 167; i++) {
		Answer = (Answer + Base.array[N][i] * power_modular(112345, i)) % mod;
	}
	
	printf("%lld", Answer);
	return 0;
}

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

Matrix matrix_power_modular (Matrix A, int Power) {
	Matrix R = { {{0}} };
	for (int i = 0; i < 167; i++) {
		R.array[i][i] = 1;
	}
	while (Power) {
		if (Power % 2) {
			R = matrix_multiply_modular (R, A);
		}
		A = matrix_multiply_modular (A, A);
		Power /= 2;
	}
	return R;
}

long long power_modular (long long A, int Power) {
	long long r = 1;
	while (Power) {
		if (Power % 2) {
			r = r * A % mod;
		}
		A = A * A % mod;
		Power /= 2;
	}
	return r;
}

(C11, 2740KB, 480ms, 제출번호 31682305)

---