def transpuesta(matriz):
m = len(matriz)
n = len(matriz[0])
return [[matriz[j][i] for j in range(m)] for i in range(n)]
def producto_punto(vector1, vector2):
return sum(vector1[i] * vector2[i] for i in range(len(vector1)))
def mult_mat(matriz1, matriz2):
return [[producto_punto(fila, columna) for columna in transpuesta(matriz2)]
for fila in matriz1]
def exp_log(a, n):
if n == 0:
return 1
if n % 2 == 0:
exp = exp_log(a, n // 2)
return exp * exp
return a * exp_log(a, n - 1)
def exp_mat(matriz, n):
if n == 1:
return matriz
if n % 2 == 0:
exp = exp_mat(matriz, n // 2)
return mult_mat(exp, exp)
return mult_mat(matriz, exp_mat(matriz, n - 1))
def g(n):
if n<2:return 2
return g(n-1)+g(n-2)
def gExpMat(n):
if n<2:return 2
coeficientes=[[1,1],[1,0]]
cbases=[[2],[2]]
return mult_mat( exp_mat(coeficientes,n-1),cbases)[0][0]
print(g(7))
print(gExpMat(7))
ZGVmIHRyYW5zcHVlc3RhKG1hdHJpeik6CiAgbSA9IGxlbihtYXRyaXopCiAgbiA9IGxlbihtYXRyaXpbMF0pCiAgcmV0dXJuIFtbbWF0cml6W2pdW2ldIGZvciBqIGluIHJhbmdlKG0pXSBmb3IgaSBpbiByYW5nZShuKV0KCmRlZiBwcm9kdWN0b19wdW50byh2ZWN0b3IxLCB2ZWN0b3IyKToKICByZXR1cm4gc3VtKHZlY3RvcjFbaV0gKiB2ZWN0b3IyW2ldIGZvciBpIGluIHJhbmdlKGxlbih2ZWN0b3IxKSkpCgpkZWYgbXVsdF9tYXQobWF0cml6MSwgbWF0cml6Mik6CiAgcmV0dXJuIFtbcHJvZHVjdG9fcHVudG8oZmlsYSwgY29sdW1uYSkgZm9yIGNvbHVtbmEgaW4gdHJhbnNwdWVzdGEobWF0cml6MildCiAgICAgICAgICBmb3IgZmlsYSBpbiBtYXRyaXoxXQoKZGVmIGV4cF9sb2coYSwgbik6CiAgaWYgbiA9PSAwOgogICAgcmV0dXJuIDEKICBpZiBuICUgMiA9PSAwOgogICAgZXhwID0gZXhwX2xvZyhhLCBuIC8vIDIpCiAgICByZXR1cm4gZXhwICogZXhwCiAgcmV0dXJuIGEgKiBleHBfbG9nKGEsIG4gLSAxKQoKZGVmIGV4cF9tYXQobWF0cml6LCBuKToKICBpZiBuID09IDE6CiAgICByZXR1cm4gbWF0cml6CiAgaWYgbiAlIDIgPT0gMDoKICAgIGV4cCA9IGV4cF9tYXQobWF0cml6LCBuIC8vIDIpCiAgICByZXR1cm4gbXVsdF9tYXQoZXhwLCBleHApCiAgcmV0dXJuIG11bHRfbWF0KG1hdHJpeiwgZXhwX21hdChtYXRyaXosIG4gLSAxKSkKCgoKCmRlZiBnKG4pOgoJaWYgbjwyOnJldHVybiAyCglyZXR1cm4gZyhuLTEpK2cobi0yKQoKZGVmIGdFeHBNYXQobik6CglpZiBuPDI6cmV0dXJuIDIKCQoJY29lZmljaWVudGVzPVtbMSwxXSxbMSwwXV0KCQoJY2Jhc2VzPVtbMl0sWzJdXQoJCglyZXR1cm4gbXVsdF9tYXQoIGV4cF9tYXQoY29lZmljaWVudGVzLG4tMSksY2Jhc2VzKVswXVswXQoKcHJpbnQoZyg3KSkKcHJpbnQoZ0V4cE1hdCg3KSkKCQ==