백준 1160번: Random Number Generator

www.acmicpc.net/problem/1160

1160번: Random Number Generator

---

수열 $ X_{n} $ 의 점화식이 $ X_{n+1} = aX_{n}+c $ (mod $ m $) 으로 주어져 있습니다.

 

일반화된 식을 얻기 위해 점화식을 계속하여 풀어보면, 다음과 같은 결과가 나옵니다.

 

$ X_{n+1}=aX_{n}+c=a^{2}X_{n-1}+c\left ( a+1 \right )=\cdots=a^{n+1}X_{0}+c\left ( a^{n}+\cdots+a+1 \right ) $

 

그런데 우리는 $ c\times \left ( a^{n}+a^{n-1}+\cdots+a+1 \right ) $ 와 같은 꼴을 이전 글에서 본 적 있습니다.

(백준 15712번: 등비수열)

 

이전 글의 행렬을 잘 참고하면, 다음과 같은 식을 얻을 수 있습니다.

 

$ \begin{pmatrix} a^{n} & 0 \\ c\left ( a^{n-1}+\cdots+a+1 \right ) & 1 \end{pmatrix} = \begin{pmatrix} a & 0 \\ c & 1 \end{pmatrix}^{n} $

 

그러면, $ X_{n} $ 을 구하는 것은 간단하게 식으로 다음과 같이 나타낼 수 있습니다.

 

$ \begin{pmatrix} X_{n} & 1 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} X_{0} & 1 \\ 0 & 0  \end{pmatrix} \times \begin{pmatrix} a & 0 \\ c & 1 \end{pmatrix}^{n} $

 

코드는 다음과 같습니다.

 

#include <stdio.h>

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

long long multiply_modular (long long x, long long y, long long M); // x * y mod M

Matrix matrix_multiply_modular_2by2 (Matrix A, Matrix B, long long M); // AB mod M

int main() {
	long long m, a, c, X0, n, g;
	scanf("%lld %lld %lld %lld %lld %lld", &m, &a, &c, &X0, &n, &g);
	
	X0 %= m;
	a %= m;
	c %= m;
	
	Matrix U, V, W;
	U.array[0][0] = X0, U.array[0][1] = 1, U.array[1][0] = 0, U.array[1][1] = 0;
	V.array[0][0] = a, V.array[0][1] = 0, V.array[1][0] = c, V.array[1][1] = 1;
	W.array[0][0] = 1, W.array[0][1] = 0, W.array[1][0] = 0, W.array[1][1] = 1;
	
	while (n > 0) { // W = V^n
		if (n & 1) {
			W = matrix_multiply_modular_2by2 (W, V, m);
		}
		V = matrix_multiply_modular_2by2 (V, V, m);
		n >>= 1;
	}
	U = matrix_multiply_modular_2by2 (U, W, m); // U * W = U * (V^n)
	
	printf("%lld", U.array[0][0] % g);
	
	return 0;
}

long long multiply_modular (long long x, long long y, long long M) {
	x %= M;
	y %= M;
	long long temp = x;
	long long result = 0;
	while (y > 0) {
		if (y & 1) {
			result = (result + temp) % M;
		}
		temp = (2 * temp) % M;
		y >>= 1;
	}
	return result;
}

Matrix matrix_multiply_modular_2by2 (Matrix A, Matrix B, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i <= 1; i++) {
		for (j = 0; j <= 1; j++) {
			result.array[i][j] = 0;
			for (k = 0; k <= 1; k++) {
				long long temp = multiply_modular(A.array[i][k], B.array[k][j], M);
				result.array[i][j] = (result.array[i][j] + temp) % M;
			}
		}
	}
	return result;
}

 

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

---

이 코드는 아이디어의 많은 부분을 다음 링크에서 따왔습니다.(www.programmersought.com/article/49606298998/)

 

사실 혼자 떠올려내기는 쉽지 않은 문제라고 생각하고, 실제로도 NOI China 2012의 1번 문제였습니다.

 

한 번 도전하고 나서 실패하고, 솔루션을 찾아보려고 2~3시간 정도 이곳저곳 둘러봤던 기억이 납니다.

 

결과적으로 올바른 솔루션을 찾았으니 다행이지만, 하도 찾는데 힘이 들어서, 이 코드를 올리고 싶어서 티스토리를 개설하기도 했습니다.