[Python] 1160번 Random Number Generator

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

---

 

24/04/15

 

 

분할 정복을 이용한 거듭제곱 문제이다. 식 정리하는 과정이 조금 까다롭다.

---

 

문제 접근 방식:

 

 

점화식이 $a_{n+1} = \alpha a_n + \beta$의 꼴이기 때문에, 이를 잘 정리하면 일반항을 얻어낼 수 있다.

 

식을 다음과 같이 정리해보자.

 

$$\begin{align} X_{n+1} &= aX_n + c \\ X_{n+1} - \alpha &= a(X_n - \alpha) \end{align} $$

이때, $X_n - \alpha = Y_n$으로 치환해보자.

$$\begin{align} Y_{n+1} &= aY_n \\ Y_n &= a^{n-1} Y_1 \\ X_n - \alpha &= a^{n-1}(X_1 - \alpha) \\ X_n &= a^{n-1}X_1 + \alpha(1 - a^{n-1}) \end{align}$$

이때, $\alpha$는 $a, c$로 표현하면 다음과 같이 표현할 수 있다.

$$ \alpha(1-a) = c \rightarrow \alpha = \frac{c}{1-a} $$

따라서, 다음과 같이 표현할 수 있다.

$$\begin{align}X_n &= a^nX_0 + \frac{c(1-a^n)}{1-a} \\X_n &= a^nX_0 + c(a^{n-1} + \cdots + 1)\end{align}$$

우리는 초항을 알고 있기 때문에 결과적으로 $a^{n-1} + \cdots +1$의 값을 빠르게 구하는 방법을 찾기만 하면 충분하다.

 

이 부분에서 풀이가 잠시 막혔었고, 아래의 블로그에서 힌트를 얻어 문제를 해결할 수 있었다.

https://blog.safespot.dev/entry/1160-Random-Number-Generator 

[1160] Random Number Generator

 

$S(n) = (a^n, a^{n-1} + \cdots + 1)$과 같이 정의하자.

그러면 $S(2n) = (a^{2n}, a^{2n-1} + \cdots + 1) = ({a^{n}}^2, (a^n + 1)(a^{n-1} + \cdots + 1))$과 같이 표현할 수 있다.

 

즉, $S(2n)$을 $S(n)$의 원소들의 곱으로 표현할 수 있다.

 

이를 활용하여 거듭제곱을 구현하면 된다.

 

위의 식들은 모두 모듈로를 고려하지 않고 계산한 것이므로, 실제로 계산할 때에는 중간 중간에 모듈로 연산을 취해주면 충분하다. 

---

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

# 1160번 Random Number Generator
# 분할 정복을 이용한 거듭제곱
'''
접근 방법:
\begin{align}
X_{n+1} & =aX_{n}+c \\
X_{n+1}-\alpha  & = a(X_{n}-\alpha) \\
\alpha(-a+1)  & = c \\
\alpha & =\frac{c}{1-a} \\
X_{n}-\alpha  & = Y_{n} \\
Y_{n+1}  & = aY_{n} \\
Y_{n} &= a^{n-1}Y_{1} \\
X_{n}-\alpha &=a^{n-1}(X_{1}-\alpha) \\
X_{n} &= a^{n-1}X_{1}+\alpha-\alpha a^{n-1} \\
X_{n} &= a^{n-1}X_{1}+\alpha(1-a^{n-1}) \\
X_{n} &= a^{n}X_{0}+\frac{c(1-a^{n})}{1-a} \\
X_{n} &= a^nX_{0}+c*(a^{n-1}+\dots+1) \\
S(n) &= (a^{n}, a^{n-1}+\dots+1) \\
S(2n) &= (a^{2n}, (a^{n}+1)(a^{n-1}+\dots+1)) \\
&= ((S(n)[0])^{2},(S(n)[0]+1)(S(n)[1]))
\end{align}
'''
import sys
input = sys.stdin.readline

m, a, c, x0, n, g = map(int, input().split())
DP = dict()
DP[1] = (a, 1)
def fast_mult(n):
    if n in DP:
        return DP[n]
    if n % 2 == 0:
        k = n//2
        p, q = fast_mult(k)
        DP[n] = ((p**2)%m, ((p+1)*q)%m)
        return DP[n]
    else:
        k = n//2
        p, q = fast_mult(k)
        DP[n] = ((a*(p**2))%m, (p**2+(p+1)*q)%m)
        return DP[n]
p, q = fast_mult(n)
ans = ((p*x0 + c*q)%m)%g
print(ans)