[Python] 30165번 Product Oriented Recurrence

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

---

 

25/06/18

 

 

선형 점화식으로 바꾸는 문제이다. 꽤나 유익하다고 생각되어 적어본다.

---

 

문제 접근 방식:

 

 

문제의 요구사항은 다음과 같다.

 

$f_x = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}$으로 정의된 점화식이 있고, $n, f_1, f_2, f_3, c$가 주어질 때 $f_n \mod (10^9 + 7)$을 구하는 것이 우리의 목적이다.

 

곱으로 되어있는 점화식이기 때문에, 우리가 흔하게 접하지 못하는 점화식의 형태이다.

 

우리가 흔하게 접하는 점화식의 형태는 덧셈의 형태이므로, 곱을 합의 형태로 바꾸기 위해 양 변에 밑을 $c$로 하는 로그를 취해주자.

 

$$\log _c f_x = 2x-6 + \log_c f_{x-1} + \log _c f_{x-2} + \log _c f_{x-3}$$

 

편의 상 $\log _c f_x = g_x$라고 하자. 그러면 아래와 같이 쓸 수 있다.

 

$$g_x = 2x-6 + g_{x-1} + g_{x-2} + g_{x-3}$$

 

이제, 거추장스러운 $2x - 6$을 비슷하게 $h_{x-1}$로 정의하면, 아래와 같이 행렬로 표현할 수 있다.

 

$$\begin{bmatrix} g_x \\ g_{x-1} \\ g_{x-2} \\ h_x \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} g_{x-1} \\ g_{x-2} \\ g_{x-3} \\ h_{x-1} \\ 1\end{bmatrix}$$

 

해당 $5 \times 5$행렬을 빠른 행렬 거듭 제곱으로 구하면 $g_n$를 빠르게 구할 수 있다.

 

$f_n = c^{g_n}$이고, 우리가 구하고자 하는 것은 $f_n \mod (10^9 + 7)$이므로, $c^{g_n} \mod (10^9 + 7)$을 구하는 것과 같다.

 

$c$와 $10^9 + 7$은 서로소이므로, 페르마의 소정리에 의해 $c^{g_n} \mod (10^9 + 7) = c^{g_n \mod 10^9 + 6} \mod (10^9 + 7)$이 된다.

 

즉, $g_n$을 구할 때 $10^9 + 6$으로 계속 모듈로를 취해주면서 구하고, 그렇게 구한 $g_n$은 결국 $g_1, g_2, g_3$에 행렬의 맨 윗줄을 곱한 무언가로 환원될 텐데, $c^{g_1} = f_1, c^{g_2} = f_2, c^{g_3} = f_3$이기 때문에 $f_1^{M_{11}}, f_2^{M_{12}}, f_3^{M_{13}}$로 작성할 수 있다. (여기서 $M$은 거듭제곱한 행렬을 의미한다)

 

최종적으로 나오는 값은 $f_3^{M_{11}} \cdot f_2^{M_{12}} \cdot f_1^{M_{13}} \cdot c^{2M_{14} + M_{15}}$가 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 30165번 Product Oriented Recurrence
# 행렬 거듭제곱
'''
접근 방법:
길어서 블로그 글로 정리
(블로그 글 링크)
'''
import sys
input = sys.stdin.readline
MOD = 1_000_000_000 + 7

def matrix_multiplication(A:list, B:list, mod:int) -> list:
    m, n, p = len(A), len(B), len(B[0])
    result = [[0 for _ in range(p)] for _ in range(m)]
    for i in range(m):
        for j in range(p):
            ele = 0
            for k in range(n):
                ele += (A[i][k]*B[k][j])%mod
            result[i][j] = ele%mod
    return result

def fast_matrix_multiply(A:list, n:int, mod:int) -> list:
    if n == 1: return A
    temp = fast_matrix_multiply(A, n//2, mod)
    if n%2 == 0:
        return matrix_multiplication(temp, temp, mod)
    else:
        return matrix_multiplication(A, matrix_multiplication(temp, temp, mod), mod)

def solve():
    N, f_1, f_2, f_3, c = map(int, input().split())
    M = [[1, 1, 1, 1, 0],
         [1, 0, 0, 0, 0],
         [0, 1, 0, 0, 0],
         [0, 0, 0, 1, 2],
         [0, 0, 0, 0, 1]]
    res = fast_matrix_multiply(M, N-3, MOD-1)
    ans = (pow(f_3, res[0][0], MOD)*pow(f_2, res[0][1], MOD)*pow(f_1, res[0][2], MOD)*pow(c, 2*res[0][3]+res[0][4], MOD))%MOD
    print(ans)

solve()