Matrix Exponentiation: 선형 점화식 fast

fast-power, Matrix Exponentiation, 행렬 거듭제곱, 행렬 지수

정의

선형 점화식을 행렬 곱으로 표현한 뒤, 행렬 거듭제곱을 log 시간에 계산하여 N 번째 항을 O(K³ log N) 에 얻는 기법. K = 상태 차원.

Fibonacci 예

\begin\{pmatrix\} F_\{n+1\} \\ F_n \end\{pmatrix\} = \begin\{pmatrix\} 1 & 1 \\ 1 & 0 \end\{pmatrix\}^n \begin\{pmatrix\} F_1 \\ F_0 \end\{pmatrix\}

using Mat = vector<vector<long long>>;
const long long MOD = 1e9 + 7;

Mat mul(const Mat& A, const Mat& B) {
    int n = A.size();
    Mat C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) if (A[i][k])
            for (int j = 0; j < n; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

Mat pow(Mat A, long long p) {
    int n = A.size();
    Mat R(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) R[i][i] = 1;
    while (p) { if (p & 1) R = mul(R, A); A = mul(A, A); p >>= 1; }
    return R;
}

O(K³ log N).

응용

• Fibonacci 를 O(log N)
• 그래프 경로 수: 인접행렬^k 의 (u, v) 원소 = u→v 길이 k 경로 수
• DFA 상태 전이

Kitamasa

일반 K-차 선형 점화식은 Polynomial Division 기법으로 O(K² log N) 까지 낮출 수 있음.

참고

• Kitamasa
• Fast Power
• Linear Algebra