[MatKor] Math is difficult

 

 

문제

수학을 좋아하는 하늘이는 수학을 싫어하는 재우에게 문제를 냈다. $i \in \mathbb{N}$과 $\alpha , \beta \in \mathbb{N}$에 대하여 $0 < a_i < a_{i+1}$와 $\alpha a_i < a_{i+2}$, 그리고 $a_{i+2} \equiv \alpha a_i (\mathrm{mod} \ \beta a_{i+1})$, $a_i \in \mathbb{N}$을 만족하는 수열 $\{ a_i \}$가 있다.
이때 자연수 $N$이 주어질 때, 위의 조건을 만족하는 수열 중 $a_N$을 최소로 만드는 수열을 $f(N) = \{ a_1, a_2, \cdots , a_N \}$라고하자. 또한, 이러한 $f(N)$에 대하여 원소의 합을 $S(N) = \sum_{i = 1}^{N} a_i$라고 하자.
수학이 어려운 재우를 도와 자연수 $N$이 주어졌을 때, $S(N)$을 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 자연수 $N$, $\alpha$, $\beta$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 10^{18}$, $1 \leq \alpha \leq 10^{18}$, $1 \leq \beta \leq 10^{18}$)

 

출력

첫 번째 줄에 $S(N)$을 출력한다. 단, 수가 너무 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

 

Subtask 1 (10 points)

$N, \alpha , \beta \leq 10$

 

Subtask 2 (15 points)

$N, \alpha , \beta \leq 1000$

 

Subtask 3 (25 points)

$N, \alpha , \beta \leq 10^6$

 

Subtask 4 (50 points)

추가적인 제약조건 없음

---

 

23/03/15

 

 

동아리 활동 중 해결했던 문제 중 하나이다. 서브태스크 문제이기 때문에 각 서브테스크 별로 해결할 수 있는 풀이를 적어보고자 한다.

---

 

문제 접근 방식:

 

먼저, 모든 Subtask를 해결하기에 앞서서, 문제의 조건이 2가지가 있는데, 1번 조건을 먼저 해석해야한다.

 

1번 조건은 $f(N)$을 어떻게 구성할 것인가?이다.

이 조건을 해석하여 구현하는 것에 따라 Subtask를 3까지 얻어낼 수 있다.

 

2번 조건은 $S(N)$을 어떻게 효율적으로 구할 것인가?이다.

 

1번 조건과 2번 조건이 동시에 수반되어야만 만점을 받을 수 있다.

내가 제시하는 코드는 만점을 받는 코드로, 각 Subtask별로 점수를 받는 코드는 따로 적지 않고 해설만 할 것이다.

 

 

먼저 1번 조건을 해결을 해야한다.

 

사실 이 문제에서 가장 어려운 부분으로, 실질적인 점화식을 구해야 되는 부분이기 때문이다.

 

먼저, $a_{i+2} \equiv \alpha a_i (\mathrm{mod} \ \beta a_{i+1})$라는 조건에 주목해 볼 필요가 있다.

 

이 말에 따르면, $a_{i+2} = \alpha a_i + k \beta a_{i+1}, k \in \mathbb{Z}$이라는 조건을 얻어낼 수 있다.

 

그 이유는 $a_{i+2} \equiv \alpha a_i (\mathrm{mod} \ \beta a_{i+1})$의 의미는, $a_{i+2}$를 $\beta a_{i+1}$로 나누었을 때 나머지가 $\alpha a_i$라는 뜻이기 때문에, $a_{i+2}$는 $\beta a_{i+1}$의 배수에 $\alpha a_i$를 더한 값으로 나타낼 수 있기 때문이다.

 

여기서 $k$를 결정짓는데에는 $\alpha a_i < a_{i+2}$라는 조건과 $a_i \in \mathbb{N}$라는 조건, $f(N)$이 $a_N$을 최소로 만드는 수열이라는 세가지 조건을 활용해야 한다.

 

먼저, $\alpha a_i < a_{i+2}$이기 때문에, 위의 점화식에 따르면, $\alpha a_i < a_{i+2} = \alpha a_i + k \beta a_{i+1}$이므로, $k \beta a_{i+1}$은 양수가 될 수 밖에 없다.

 

여기서 $a_i \in \mathbb{N}$라는 조건을 이용하면, $k$는 양수인 정수, 즉, 자연수가 될 수 밖에 없다.

 

이때 $f(N)$이 $a_N$을 최소로 만드는 수열이라고 했으므로, $a_N$이 최소가 되려면 $k$가 $1$이 되야만 $a_N$이 최소가 될 수 있다.

 

따라서, 최종적인 점화식은 $a_{i+2} = \alpha a_i + \beta a_{i+1}$가 된다.

 

초기항을 결정을 지으려면, $0 < a_i < a_{i+1}$과 $f(N)$이 $a_N$을 최소로 만드는 수열이라는 조건을 사용하면, $a_1 = 1, a_2 = 2$라는 결론을 얻어낼 수 있다.

 

따라서 초기항 2개와 최종적인 점화식을 활용하여 각각의 $a_i$를 구하여 $N$까지의 합을 구해 $10^9 + 7$로 나누어주면 해결할 수 있다.

 

Subtask 1은 이 점화식을 재귀적으로 구현하면 해결할 수 있다. 재귀적으로 해결하면 10까지의 작은 경우는 가능하나, Subtask 2는 해결할 수 없을 것이다.

 

Subtask 2와 3은 이 점화식과 메모이제이션 기법을 활용, 즉 DP를 적용하면 해결할 수 있을 것이다.

 

 

하지만 Subtask 4는 $10^{18}$이라는 아주 큰 제한을 가지고 있기 때문에 DP로 풀 수 없다.

 

이때 2번 조건을 해결하면 된다.

 

$S(N)$을 어떻게 효율적으로 구할 것인가?

 

결국 우리가 원하는 것은 아래 식과 같다.

 

$$S = \sum_{i = 1}^{N} a_i$$

 

또한, 우리는 아래의 점화식을 알고 있다.

 

$$a_{i+2} = \alpha a_i + \beta a_{i+1} , a_1 = 1, a_2 = 2$$

 

이 점화식의 모든 변에 $\sum$ 기호를 씌워주면 아래와 같이 변할 수 있다.

 

$$\sum_{i = 1}^{N-2} a_{i+2} = \alpha \sum_{i = 1}^{N-2} a_{i} + \beta \sum_{i = 1}^{N-2} a_{i+1}$$

 

이를 $S$를 활용하여 정리하면 아래와 같이 정리할 수 있다.

 

$$S - a_1 - a_2 = \alpha (S - a_N - a_{N-1}) + \beta (S - a_N - a_1)$$

$$S - 3 = \alpha S - \alpha a_N - \alpha a_{N-1} + \beta S - \beta a_N - \beta$$

$$(\alpha + \beta - 1)S = (\alpha + \beta)a_N + \alpha a_{N-1} + \beta - 3$$

$$S = \frac{(\alpha + \beta)a_N + \alpha a_{N-1} + \beta - 3} {\alpha + \beta - 1}$$

 

결국, 우리는 $a_N$과 $a_{N-1}$의 값만 빠르게 찾아 낼 수 있다면, 이 식을 토대로 S의 값을 빠르게 구할 수 있는 것이다.

 

선형 점화식이 주어져 있을 때, $N$번째 항을 빠르게 찾아낼 수 있는 방법은 행렬을 이용한 선형 점화식 단순화 + 분할정복을 이용한 거듭제곱을 섞으면 $N$번째 항을 $O(log \ N)$의 시간 복잡도로 구할 수 있다.

 

우리는 $10^9 + 7$, 즉, 소수로 나눈 나머지를 구하고 싶어하므로, $\alpha + \beta - 1$의 $10^9 + 7$에 대한 역원을 페르마 소정리를 통해 구할 수 있다.

 

만약 파이썬이라면 pow($\alpha + \beta - 1$, $-1$, MOD)로 역원을 구할 수 있다.

 

이 역원을 곱해주고 MOD를 취해주면 문제를 해결할 수 있다.

---

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

def matrixmult(A, B, mod, k):
    K = [[0 for _ in range(k)] for _ in range(k)]
    for i in range(k):
        for j in range(k):
            ele = 0
            for m in range(k):
                ele += (A[i][m]*B[m][j])%mod
            K[i][j] = ele%mod
    return K
def multiply(A, n, mod, k):  # 행렬, 몇제곱할건지, 나머지, 행렬크기
    if n == 1:
        return A
    temp = multiply(A, n//2, mod, k)
    if n%2 == 0:
        return matrixmult(temp, temp, mod, k)
    else:
        return matrixmult(A, matrixmult(temp, temp, mod, k), mod, k)
def linear_recurrence(alpha, beta, n, mod):
    matrix = [[beta, alpha], [1, 0]]
    if n < 2:
        if n == 0:
            return 1
        else:
            return 2
    else:
        K = multiply(matrix, n-1, mod, 2)
        val = (2*K[0][0] + K[0][1]) % mod
        return val
MOD = 1000000007
N, alpha, beta = map(int, input().split())
an = linear_recurrence(alpha, beta, N-1, MOD)
an1 = linear_recurrence(alpha, beta, N-2, MOD)
k = (alpha+beta)%MOD
a = alpha%MOD
b = (beta-3)%MOD
l = pow((alpha+beta-1), -1, MOD)
if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    print((((k*an)%MOD + (a*an1)%MOD + b)%MOD)*l%MOD)