Matrix for Linear Recurrence Relation
in Study / Computer science on Matrix
Algorithm
- Linear Recurrence Relation (선형 점화식)
- an = Sum of (constant x previous a)
- ex) Fibonacci : an = an-1 + an-2
- It can work out through DP
- It can work out through matrix (행렬) more effectively than DP (O(logN))
Fibonacci
- an = an-1 + an-2
- Thinking
1 1
Let A =
1 0
a3 a2
= A x (a3 = a1 + a2)
a2 a1
a4 a3 a2
= A x = A**2 x
a3 a2 a1
.
.
.
.
.
a(n+1) a2
= A**(n-1) x
an a1
b c
∴ If calculated A**(n-1) =
d e
an = d x a2 + e x a1
- Code
n = int(input())
def multiply(A, B):
res = [[0 for i in range(2)] for i in range(2)]
for i in range(2):
for j in range(2):
for k in range(2):
res[i][j] += (A[i][k] * B[k][j])
return res
def modpow(A, r):
res = A
intermediate = A
flag = True
for i in range(60):
if r < (1 << i):
break
if r & (1 << i) != 0:
if flag:
res = intermediate
flag = False
else:
res = multiply(res, intermediate)
intermediate = multiply(intermediate, intermediate)
return res
A = [[1, 1], [1, 0]]
mod = 10 ** 9
res = modpow(A, n - 1)
print(res[1][0] + res[1][1])
- multiply : multiplication of matrix
- modpow : iterative square method for matrix
Other Example
- an = 2an-1 + an-2
2 1
Let A =
1 0
a3 a2
= A x (a3 = a1 + 2 x a2)
a2 a1
a4 a3 a2
= A x = A**2 x
a3 a2 a1
.
.
.
- an = an-1 + an-2 + an-3
1 1 1
Let A = 1 0 0
0 1 0
a4 a3
a3 = A x a2 (a4 = a1 + a2 + a3)
a2 a1
a5 a4 a3
a4 = A x a3 = A**2 x a2
a3 a2 a1
.
.
.
Problem
This is the private repository where I can only review my notes
Repository