Matrix DP & Fast Linear Recurrences — அணி DP & விரைவு மீள்ச்சூத்திரம்

அணி பெருக்கம் — நடை நீளம்; விரைவு exponent.

உண்மை உலகில் இது ஏன் முக்கியம்?

k நடை; மீள்ச்சூத்திரம்.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

T^k @ dp.

Pythonில் முயற்சி செய்வோம்

def mat_mul(A: list[list[int]], B: list[list[int]], mod: int) -> list[list[int]]:
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k]:
                for j in range(n):
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C


def mat_pow(M: list[list[int]], e: int, mod: int) -> list[list[int]]:
    n = len(M)
    R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    while e:
        if e & 1:
            R = mat_mul(R, M, mod)
        M = mat_mul(M, M, mod)
        e //= 2
    return R


fib = [[1, 1], [1, 0]]
print(mat_pow(fib, 10, 10**9 + 7)[0][1])

அடிக்கடி நேரும் தவறுகள்

• பரிமாணம்.
• mod.

முக்கியச் சுருக்கக் குறிப்புகள்

• k=0,1 சோதனை.