SHARE
TWEET

Untitled

a guest Oct 18th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Matrix:
  2.     Q = [[0, 1],
  3.          [1, 1]]
  4.  
  5.     def __init__(self):
  6.         self.__memo = {} #add memorization
  7.  
  8.     def __multiply_matrices(self, M1, M2):# multiply two 2x2 matrices line by column
  9.         a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
  10.         a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
  11.         a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
  12.         a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
  13.         r = [[a11, a12], [a21, a22]]
  14.         return r
  15.  
  16.     def __get_matrix_power(self, M, p):
  17.         if p == 1:# if p was 1 we return matrix itself
  18.             return M
  19.         if p in self.__memo:# if we've already counted this power we return reminded matrix
  20.             return self.__memo[p]
  21.         K = self.__get_matrix_power(M, int(p/2)) # recursively power matrix to p/2 power
  22.         R = self.__multiply_matrices(K, K) #matrix to matrix power = 2
  23.         self.__memo[p] = R# remind it
  24.         return R
  25.  
  26.     def get_num(self, n):
  27.         if n == 0:#start num
  28.             return 0;
  29.         if n == 1:#start num
  30.             return 2;
  31.         powers = []
  32.         p = 0
  33.         for digit in reversed(bin(n-1)[2:]):# get bit representation of number
  34.             if digit == '1':
  35.                 powers.append(int(pow(2, p)))# if bit = 1 then there was 1*2^p in number -> remind 2^p
  36.             p += 1
  37.         matrices = [self.__get_matrix_power(Matrix.Q, p)
  38.                     for p in powers] #save all intermediate result
  39.         while len(matrices) > 1:
  40.             M1 = matrices.pop()
  41.             M2 = matrices.pop()
  42.             R = self.__multiply_matrices(M1, M2)#multiply them
  43.             matrices.append(R)
  44.  
  45.         k = matrices[0][0][0] + matrices[0][1][0]# last matrix will contain all needed results
  46.         mm = matrices[0][0][1] + matrices[0][1][1]
  47.         return k + mm
  48.  
  49. mat = Matrix()
  50. tt = int(input())
  51. num = mat.get_num(tt)
  52. print(num)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top