ABC 293 복기 E - Geometric Progression - 행렬곱 배우기 -

1. 문제

 

E - Geometric Progression (atcoder.jp)

E - Geometric Progression

 

정수 A,X,M이 주어질 때, $$\sum_{k=0}^{X-1} A^{k}$$ 를 구하는 아주 간단한 문제

 

2. 풀이1

 

이미 재귀로 푸는 방법을 배운적 있다

 

컴퓨터가 등비수열의 합을 구하는 방법 (tistory.com)

컴퓨터가 등비수열의 합을 구하는 방법

 

3. official editorial

 

editorial에서 제공하는 방법을 보면...

 

$$a_{n} = \sum_{k=0}^{n-1} A^{k}$$ 이라고 하자.

 

그러면 $a_{0} = 0$, $a_{n+1} = Aa_{n} + 1$이다.

 

이를 행렬로 표현하면 다음과 같다

 

$$\begin{pmatrix} a_{n+1} \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \\ \end{pmatrix}\begin{pmatrix} a_{n} \\ 1 \end{pmatrix}$$

 

따라서 n = 0이면...

 

$$\begin{pmatrix} a_{1} \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \\ \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

 

n=1이면...

 

$$\begin{pmatrix} a_{2} \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \\ \end{pmatrix}\begin{pmatrix} a_{1} \\ 1 \end{pmatrix}$$

 

위의 식을 그대로 대입하면 다음을 얻는다..

 

$$\begin{pmatrix} a_{2} \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \\ \end{pmatrix}^{2}\begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

 

 

구하고자 하는건 $a_{X} = \sum_{k=0}^{X-1} A^{k}$이므로, n = X가 될 때까지 반복해서 곱하면..

 

$$\begin{pmatrix} a_{X} \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \\ \end{pmatrix}^{X}\begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

 

따라서   $$\begin{pmatrix} A & 1 \\ 0 & 1 \\ \end{pmatrix}^{X}$$ 만 구할 수 있다면, 원하는 값을 구할 수 있게 된다

 

 

--------------------------------------------------------------------------------------------------------------------------

 

먼저 두 행렬의 곱은 어떻게 구할 수 있을까

 

A,B의 곱 C의 ij번째 원소는... 모든 k = 1,2,...에 대하여.. a의 ik번째 원소와 b의 kj번째 원소의 곱의 합이다.

 

$$c_{ij} = \sum_{k} a_{ik}b_{kj}$$

 

mod연산의 성질로부터, 곱셈한 결과를 계속 mod연산으로 나눠서 더해준다.

 

def matrix_multiplication(a,b,n,mod):

    mul = [[0] * n for _ in range(n)]

    for i in range(n):
        
        for j in range(n):
            
            for k in range(n):
                
                mul[i][j] += a[i][k] * b[k][j]

                mul[i][j] %= mod
    
    return mul

 

다음 행렬의 거듭제곱은 어떻게 만들 수 있을까..?

 

분할정복을 이용한 거듭제곱 코드를 다시 살펴보자

 

def power(a,n):
    
    result = 1
    
    while n:
        
        if n % 2 == 1:
            
            result *= a
        
        
        a *= a
        
        n //= 2
    
    return result

 

 

처음에 result = 1을 초기화하고, n이 1 이상일 때까지 반복문을 수행

 

n이 홀수이면 result에 지금까지 거듭제곱한 a를 곱해주고

 

n이 짝수이면 a에 a를 거듭제곱해주고

 

n은 2로 나눈 몫으로 변경해준다.

 

예를 들어 n = 6이면..

 

$result = 1$

 

$a = a^{2}$

 

$n = 3$

 

-------------------------

 

$result = a^{2}$

 

$a = a^{4}$

 

$n = 1$

 

-------------------------

 

$result = a^{6}$

 

$a = a^{8}$

 

$n = 0$

 

행렬의 거듭제곱도 마찬가지다.

 

행렬에서 항등원(result = 1)은 모든 대각원소가 1인 항등행렬

 

지수가 1 이상이면 반복문을 수행

 

지수가 홀수이면 result와 a를 곱해주고

 

지수가 짝수이면 a에 a를 곱해주고

 

지수를 절반 나눠준다

 

def matrix_exponentiation(a,b,n,mod):

    result = [[0]*n for _ in range(n)]
    
    #항등행렬을 만든다
    for i in range(n):
        
        result[i][i] = 1
    
    while b:
        
        if b & 1: #if b % 2 == 1:
            
            result = matrix_multiplication(result,a,n,mod)
        
        a = matrix_multiplication(a,a,n,mod)
        b >>= 1 #b //= 2
    
    return exp

 

 

근데 이건 다시봐도 왜 되는건지 볼때마다 신기하다... 

 

-----------------------------------------------------------------------------------------------------------------------------

 

아무튼 이제 구하고자 하는 결과는..?

 

$$\begin{pmatrix} A & 1 \\ 0 & 1 \\ \end{pmatrix}$$ 으로 초기화하고 X번 거듭제곱한다.

 

그 결과가 

 

$$\begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}$$ 라고 해보자.

 

$$\begin{pmatrix} a_{X} \\ 1 \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix}=\begin{pmatrix} b \\ d \end{pmatrix}$$

 

그러므로, $a_{X} = b$이다. 즉, 거듭제곱한 결과의 0,1 원소가 정답이다.

 

a,x,m = map(int,input().split())

matrix = [[a,1],[0,1]]

n = 2

print(matrix_exponentiation(matrix,x,n,m)[0][1])