백준 30165번: Product Oriented Recurrence

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

30165번: Product Oriented Recurrence

---

고등학교 수학에서 종종 다루는 형태의 점화식입니다.

---

$c$에 대한 로그를 씌우면 점화식은 다음과 같이 변형됩니다.

$$ \log_{c}f_{x} = 2x-6 + \log_{c}f_{x-1} + \log_{c}f_{x-2} + \log_{c}f_{x-3} $$

이제 $A_{x}$와 $B_{x}$를 다음과 같이 정의합니다.

$$ A_{x} = \log_{c}f_{x} \;\; (x \geq 1) $$

$$ B_{x} = 2x-6 \;\; (x \geq 4) $$

이로부터 다음의 행렬 점화식을 구성할 수 있습니다.

$$ \begin{bmatrix} A_{x} \\ A_{x-1} \\ A_{x-2} \\ B_{x} \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} A_{x-1} \\ A_{x-2} \\ A_{x-3} \\ B_{x-1} \\ 1 \end{bmatrix} $$

이제 행렬 $M$이

$$ M = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

라고 하면,

$$ A_{x} = (M^{x-3})_{14} \times B_{3} + (M^{x-3})_{15} + \sum_{i=1}^{3} (M^{x-3})_{1i} \times A_{4-i} $$

인 것을 알 수 있습니다. 이때, $B_{3}$의 값을 올바르게 정해야 합니다.

 

위 식에 $x=4$를 대입하면,

$$ A_{4} = B_{3} + 0 + A_{3} + A_{2} + A_{1} $$

입니다. 그런데 문제에서의 정의에 따르면,

$$ A_{4} = log_{c}f_{4} = 2 + A_{3} + A_{2} + A_{1} $$

이므로 다음을 알 수 있습니다.

$$ B_{3} = 2 $$

언뜻 보기엔 점화식을 만족하지 않는 것처럼 보이지만, 점화식이 성립하는 범위 밖에서는 그 수열은 어떤 값이라도 가질 수 있기 때문에 틀린 것이 아닙니다.

---

이제 $A_{x}$를 구했으니 이로부터 $f_{x}$를 복원합니다.

$$ f_{x} = c^{A_{x}} = c^{2 \times (M^{x-3})_{14} + (M^{x-3})_{15} + \sum_{i=1}^{3} (M^{x-3})_{1i} \times A_{4-i}} $$

$$ = c^{(M^{x-3})_{13} \times A_{1}} \times c^{(M^{x-3})_{12} \times A_{2}} \times c^{(M^{x-3})_{11} \times A_{3}} \times c^{2 \times (M^{x-3})_{14} + (M^{x-3})_{15}} $$

$$ = f_{3}^{(M^{x-3})_{11}} \times f_{2}^{(M^{x-3})_{12}} \times f_{1}^{(M^{x-3})_{13}} \times c^{2 \times (M^{x-3})_{14} + (M^{x-3})_{15}} $$

이 과정에서, 이산 로그는 굳이 필요하지는 않습니다.

---

한편, $(M^{x-3})_{ij}$ 을 곧이곧대로 구하는 건 당연히 오버플로우가 발생하므로, 적당한 모듈로를 취해줘야 합니다.

 

이 문제에서는, $(M^{x-3})_{ij}$ 은 $f_{x}$의 식에서 지수 부분에 위치한 값입니다.

 

이런 경우, Euler's Theorem을 쓸 수 있습니다. (a,p는 서로소, p는 소수)

$$ a^{p-1} \equiv 1 \;\; (mod \; P)$$

따라서 행렬을 거듭제곱할 때 행렬의 각 원소에 모듈로 $P-1$을 취해주면 됩니다.

 

다음은 제 코드입니다.

#include <stdio.h>
#define matmod 1000000006 // totient(p) = p - 1
#define intmod 1000000007

long long power_modular (long long X, long long Y);

typedef struct {
    long long array[5][5];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, long long P);

int main() {
    
    long long n, f1, f2, f3, c;
    scanf("%lld %lld %lld %lld %lld", &n, &f1, &f2, &f3, &c);
    
    Matrix Base =
    {{
        {1, 1, 1, 1, 0},
        {1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 1, 2},
        {0, 0, 0, 0, 1}
    }};
    Base = matrix_power_modular(Base, n - 3);
    
    long long answer = 1;
    answer = answer * power_modular(f3, Base.array[0][0]) % intmod;
    answer = answer * power_modular(f2, Base.array[0][1]) % intmod;
    answer = answer * power_modular(f1, Base.array[0][2]) % intmod;
    answer = answer * power_modular(c, 2 * Base.array[0][3] + Base.array[0][4]) % intmod;
    
    printf("%lld", answer);
    return 0;
}

long long power_modular (long long X, long long Y) {
    long long result = 1;
    while (Y) {
        if (Y % 2) {
            result = result * X % intmod;
        }
        X = X * X % intmod;
        Y /= 2;
    }
    return result;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B) {
    Matrix result = {{{}}};
    for (int i = 0; i < 5; i++) {
        for (int k = 0; k < 5; k++) {
            for (int j = 0; j < 5; j++) {
                result.array[i][j] = (result.array[i][j] + A.array[i][k] * B.array[k][j]) % matmod;
            }
        }
    }
    return result;
}

Matrix matrix_power_modular (Matrix A, long long P) {
    Matrix result = {{{}}};
    for (int i = 0; i < 5; i++) result.array[i][i] = 1;
    while(P) {
        if (P % 2) {
            result = matrix_multiply_modular(result, A);
        }
        A = matrix_multiply_modular(A, A);
        P /= 2;
    }
    return result;
}

(C11, 0ms, 1116KB, 제출번호 67084038)

---

이 문제는 Codeforces Round #566 (Div.2)에 E번으로 출제된 문제라고 합니다.

 

에디토리얼에서는, 소인수분해를 통해 접근하고 있는데 물론 충분히 가능한 방법이긴 합니다만, 행렬의 크기가 커질 수 있겠습니다.

 

댓글에서는 이산 로그를 쓰거나, 점화식을 바꾸는 접근을 하고 있는데 이산 로그는 증명 과정에서 쓸 순 있겠으나 제 생각엔 필수적인 건 아닌 것 같습니다.

 

시간이 나면 다른 점화식으로도 풀어보고 싶습니다.