หาพจน์ที่ N ด้วย Matrix Exponentiation ใน C++

ภาพรวมปัญหา

หาพจน์ที่ N ของความสัมพันธ์แบบเวียนเกิด (Recurrence):

T(n) = 2·T(n-1) + 3·T(n-2)
T(0) = 1, T(1) = 1

ตัวอย่าง

อินพุต

N = 4

เอาต์พุต

41

วิธีแก้ปัญหา

วิธีที่ 1: Recursion - O(2ⁿ) ช้า

วิธีที่ 2: Matrix Exponentiation - O(log N) ⭐

แปลง Recurrence เป็นการคูณเมทริกซ์:

State Vector: [T(n), T(n-1)]ᵀ
Transform Matrix: [[2, 3], [1, 0]]

[T(n)  ]   = [2 3] × [T(n-1)]
[T(n-1)]     [1 0]   [T(n-2)]

T(n) = (Transform Matrix)^(n-1) × Initial Vector

โค้ดตัวอย่าง (Matrix Exponentiation)

#include <iostream>
using namespace std;

#define MOD 1000000009

long calcNthTerm(long n) {
    if (n <= 1) return 1;
    n--;
    
    long resultantMat[2][2] = {{1, 0}, {0, 1}};  // Identity
    long transMat[2][2] = {{2, 3}, {1, 0}};
    
    while (n) {
        if (n & 1) {
            long tempMat[2][2];
            tempMat[0][0] = (resultantMat[0][0] * transMat[0][0] + resultantMat[0][1] * transMat[1][0]) % MOD;
            tempMat[0][1] = (resultantMat[0][0] * transMat[0][1] + resultantMat[0][1] * transMat[1][1]) % MOD;
            tempMat[1][0] = (resultantMat[1][0] * transMat[0][0] + resultantMat[1][1] * transMat[1][0]) % MOD;
            tempMat[1][1] = (resultantMat[1][0] * transMat[0][1] + resultantMat[1][1] * transMat[1][1]) % MOD;
            
            resultantMat[0][0] = tempMat[0][0];
            resultantMat[0][1] = tempMat[0][1];
            resultantMat[1][0] = tempMat[1][0];
            resultantMat[1][1] = tempMat[1][1];
        }
        n >>= 1;
        
        long tempMat[2][2];
        tempMat[0][0] = (transMat[0][0] * transMat[0][0] + transMat[0][1] * transMat[1][0]) % MOD;
        tempMat[0][1] = (transMat[0][0] * transMat[0][1] + transMat[0][1] * transMat[1][1]) % MOD;
        tempMat[1][0] = (transMat[1][0] * transMat[0][0] + transMat[1][1] * transMat[1][0]) % MOD;
        tempMat[1][1] = (transMat[1][0] * transMat[0][1] + transMat[1][1] * transMat[1][1]) % MOD;
        
        transMat[0][0] = tempMat[0][0];
        transMat[0][1] = tempMat[0][1];
        transMat[1][0] = tempMat[1][0];
        transMat[1][1] = tempMat[1][1];
    }
    
    return (resultantMat[0][0] * 1 + resultantMat[0][1] * 1) % MOD;
}

int main() {
    long n = 5;
    cout << n << "th term using matrix exponentiation is " << calcNthTerm(n);
    return 0;
}

เอาต์พุต

5th term using matrix exponentiation is 121

สรุป

Matrix Exponentiation เร็วกว่า Recursion มากสำหรับ N ใหญ่ ใช้ Binary Exponentiation บนเมทริกซ์