• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?