• Numbers (Small)에서 n의 범위가 커진 문제. n제곱 계산 과는 완전히 동일한 문제이다.
• 알고리즘 보다는 수학 문제에 더 가까운 문제. 고등수학 지식이 필요한건 아니지만 수학적인 아이디어가 필요하다.
• 문제가 임의의 $a+\sqrt{b}$의 꼴이 아니라, $3+\sqrt{5}$로 주어진 것은 이유가 있다. $3-\sqrt{5}<1$ 이기 때문이다. 식을 바꿔서 $a_n = (3+\sqrt{5})^n + (3-\sqrt{5})^n$ 을 구해보자. 이 식에서는 $\sqrt{b}$ 항에 붙는 계수의 합이 0이 되기 때문에, 식의 값이 정수로 나온다. $(3-\sqrt{5})^n$ 는 1보다 작으므로 $(3+\sqrt{5})^n$ = $a_n - 0.xxxx$이다. 정수부만 구하면 $a_n - 1$ 이 된다.
• 그러면 이제 $a_n = (3+\sqrt{5})^n + (3-\sqrt{5})^n$ 을 구하자. $\alpha =3+\sqrt{5}$, $\beta = 3-\sqrt{5}$라고 하면, $\alpha$와 $\beta$를 근으로 하는 이차방정식은 $x^2 - 6x + 4 = 0$ 이다. $\alpha^n= 6\alpha^{n-1} + 4\alpha^{n-2}$, $\beta^n= 6\beta^{n-1} + 4\beta^{n-2}$ 이므로 두 식을 합치면 $\alpha^n + \beta^n = 6(\alpha^{n-1} + beta^{n-1}) + 4(\alpha^{n-2} +\beta^{n-2})$ 이므로 $a_n = 6(a_{n-1}) - 4(a_{n-2})$ 라는 점화식을 얻는다.
• 이러한 선형 점화식은 행렬 거듭제곱형태로 표현해서 O(logn)에 구할수 있다. T개의 케이스에 대해서 구하는 총 시간복잡도는 O(Tlogn).
• 문제에서 실제로 구하는 것은 a_n % 1000 인데, 점화식이 기존의 2개 항에만 의존하므로, a_n%1000 은 최대 1000*1000 길이의 사이클을 갖게 된다. 사이클의 길이까지의 (a_i % 1000) 값을 미리 계산해놓는다면, 각 케이스의 값을 O(1)에 구할수도 있다.. 이렇게 할 경우 총 시간 복잡도는 O(1000*1000 + T) = O(T) 가 된다. 이방법으로 구현은 안해봤는데.. 다른 사람들 코드를 보니 실제 사이클의 길이는 102 정도밖에 안되는 것같다.

"""Solution code for "BOJ 12925. Numbers".

- Problem link: https://www.acmicpc.net/problem/12925
- Solution link: http://www.teferi.net/ps/problems/boj/12925

Tags: [Math]
"""

from teflib import combinatorics

MOD = 1000
COEF = [6, -4]  # A(n)=6A(n-1)-4A(n-2)  ( A(n) = (3+sqrt(5))^n + (3-sqrt(5))^n )
SEED = [2, 6]  # A(0)=2, A(1)=6


def main():
    T = int(input())
    for i in range(T):
        n = int(input())

        answer = combinatorics.linear_homogeneous_recurrence(
            COEF, SEED, n, MOD) - 1
        print(f'Case #{i + 1}: {answer:>03}')


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.linear_homogeneous_recurrence