문제
수학을 좋아하는 하늘이는 수학을 싫어하는 재우에게 문제를 냈다. $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)'알고리즘 > 그 외 문제들' 카테고리의 다른 글
| [구름 알고리즘 먼데이 챌린지] 3주차 4번 순환하는 수로 (2) | 2022.11.07 |
|---|
