등비수열의 합은 $ a+ar+ar^{2}+\cdots+ar^{n-1} $ 입니다.
이는 a로 묶어보면 $ a\left ( 1+r+r^{2}+\cdots+r^{n-1} \right ) $ 입니다.
조금 뜬금없지만 이 행렬을 관찰하면,
$ \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix} $
이 사실을 발견할 수 있습니다.
$ \begin{pmatrix} r^{2} & 0 \\ a\left ( r+1 \right ) & 1 \end{pmatrix} = \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix}^{2} $
같은 행렬을 한 번 더 곱하게 되면,
$ \begin{pmatrix} r^{3} & 0 \\ a\left ( r^{2}+r+1 \right ) & 1 \end{pmatrix} = \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix}^{3} $ 이 나옵니다.
즉, 이런 성질을 발견할 수 있습니다.
$ \begin{pmatrix} r^{n} & 0 \\ a\left ( r^{n-1}+\cdots+r+1 \right ) & 1 \end{pmatrix} = \begin{pmatrix} r & 0 \\ a & 1 \end{pmatrix}^{n} $
그러므로 우리는 어떤 행렬을 n제곱 해야 문제의 정답을 도출할 수 있을 지 알 수 있었습니다.
구현한 코드는 다음과 같습니다.
#include <stdio.h>
typedef struct {
long long array[2][2];
} Matrix;
Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M);
Matrix matrix_power_modular (Matrix A, long long K, long long M);
int main() {
long long a, r, n, mod;
scanf("%lld %lld %lld %lld", &a, &r, &n, &mod);
Matrix Base;
Base.array[0][0] = r, Base.array[0][1] = 0, Base.array[1][0] = a, Base.array[1][1] = 1;
Base = matrix_power_modular (Base, n, mod);
printf("%lld", Base.array[1][0]);
return 0;
}
Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M) {
Matrix result;
int i, j, k;
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
result.array[i][j] = 0;
for (k = 0; k < 2; k++) {
long long temp = (A.array[i][k] * B.array[k][j]) % M;
result.array[i][j] = (result.array[i][j] + temp) % M;
}
}
}
return result;
}
Matrix matrix_power_modular (Matrix A, long long K, long long M) {
Matrix result;
result.array[0][0] = result.array[1][1] = 1;
result.array[0][1] = result.array[1][0] = 0;
while (K > 0) {
if (K & 1) {
result = matrix_multiply_modular(result, A, M);
}
A = matrix_multiply_modular(A, A, M);
K >>= 1;
}
return result;
}
(C11, 1116KB, 0ms, 제출번호 25772793)
처음에는, $ \left ( r-1 \right )^{-1} $ 의 mod 값을 구하려했는데
페르마의 소정리나 오일러 정리를 쓰기 어려운 환경이므로 생각을 바꾼 게 유효했습니다.
'분할 정복을 이용한 거듭제곱 > 행렬 거듭제곱' 카테고리의 다른 글
백준 13246번: 행렬 제곱의 합 (0) | 2021.02.19 |
---|---|
백준 1160번: Random Number Generator (0) | 2021.01.29 |
백준 14440번: 정수 수열 (0) | 2021.01.29 |
백준 11366번: Tons of Orcs, no Fibbin' (0) | 2021.01.29 |
백준 11440번: 피보나치 수의 제곱의 합 (0) | 2021.01.29 |