3344 - Fibonacci2

Cerința

Șirul lui Fibonacci este definit astfel:

Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2. Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013.

Restricții și precizări

• 1 ≤ n ≤ 2.000.000.000

Exemplu:

Intrare

6

Ieșire

8

Explicație

Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...

Rezolvare

MOD = 666013

class Mat:
    def __init__(self, mat):
        self.mat = mat

nullMat = Mat([[1, 0], [0, 1]])
initMat = Mat([[1, 1], [1, 0]])

def prod(a, b):
    ret = Mat([[0, 0], [0, 0]])
    ret.mat[0][0] = (a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]) % MOD
    ret.mat[0][1] = (a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]) % MOD
    ret.mat[1][0] = (a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]) % MOD
    ret.mat[1][1] = (a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]) % MOD
    return ret

def pwr(mat, n):
    if n == 0:
        return nullMat
    if n % 2 == 1:
        return prod(mat, pwr(prod(mat, mat), n // 2))
    return pwr(prod(mat, mat), n // 2)

def verifica_restrictii(n):
    if 1 <= n <= 2000000000:
        return True
    else:
        print("Datele nu corespund restrictiilor impuse")
        return False

def main():
    n = int(input())
    if verifica_restrictii(n):
        result = pwr(initMat, n)
        print(result.mat[0][1])

if __name__ == "__main__":
    main()