




'''simple docstring'''



import timeit





class     lowerCAmelCase   :


       def __init__(   self    ,  __SCREAMING_SNAKE_CASE  )      ->  Any:



            '''simple docstring'''




            if isinstance(__SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE  ):  # Initializes a matrix identical to the one provided.
                 __snake_case    					=  arg
                 __snake_case    					=  len(__SCREAMING_SNAKE_CASE  )
            else:  # Initializes a square matrix of the given size and set values to zero.
                 __snake_case    					=  arg
                 __snake_case    					=  [[0 for _ in range(self.n  )] for _ in range(self.n  )]




       def __mul__(   self    ,  __SCREAMING_SNAKE_CASE  )      ->  List[Any]:



            '''simple docstring'''




            __snake_case    					=  Matrix(self.n  )
            for i in range(self.n  ):
                 for j in range(self.n  ):
                      for k in range(self.n  ):
                           matrix.t[i][j] += self.t[i][k] * b.t[k][j]
            return matrix







def 			_UpperCamelCase (_lowerCamelCase							:     List[str]   ,	_lowerCamelCase							:     int	)->   int:




     '''simple docstring'''





     __snake_case    					=  Matrix([[1, 0], [0, 1]]	)
     while b > 0:
          if b & 1:
               matrix *= a
          a *= a
          b >>= 1
     return matrix







def 			_UpperCamelCase (_lowerCamelCase							:     Optional[Any]   ,	_lowerCamelCase							:     Any   ,	_lowerCamelCase							:     int	)->   Optional[Any]:




     '''simple docstring'''





     if n == 1:
          return fa
     elif n == 2:
          return fa
     __snake_case    					=  Matrix([[1, 1], [1, 0]]	)
     __snake_case    					=  modular_exponentiation(lowerCAmelCase__   ,	n - 2	)
     return fa * matrix.t[0][0] + fa * matrix.t[0][1]







def 			_UpperCamelCase (_lowerCamelCase							:     Any   ,	_lowerCamelCase							:     Union[str, Any]   ,	_lowerCamelCase							:     List[str]	)->   Dict:




     '''simple docstring'''





     if n == 1:
          return fa
     elif n == 2:
          return fa

     __snake_case    					=  fa
     __snake_case    					=  fa
     n -= 2

     while n > 0:
          __snake_case    					=  fn_a + fn_a, fn_a
          n -= 1

     return fn_a







def 			_UpperCamelCase ()->   str:




     '''simple docstring'''





     __snake_case    					=  '\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n'
     __snake_case    					=  'fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'
     __snake_case    					=  timeit.timeit(setup=lowerCAmelCase__   ,	stmt=lowerCAmelCase__   ,	number=1_00	)
     print('''With matrix exponentiation the average execution time is '''   ,	exec_time / 1_00	)
     return exec_time







def 			_UpperCamelCase ()->   List[Any]:




     '''simple docstring'''





     __snake_case    					=  '\nfrom random import randint\nfrom __main__ import simple_fibonacci\n'
     __snake_case    					=  'simple_fibonacci(randint(1,70000), 1, 1)'
     __snake_case    					=  timeit.timeit(setup=lowerCAmelCase__   ,	stmt=lowerCAmelCase__   ,	number=1_00	)
     print(
         '''Without matrix exponentiation the average execution time is '''   ,	exec_time / 1_00	)
     return exec_time







def 			_UpperCamelCase ()->   Dict:




     '''simple docstring'''





     matrix_exponentiation_time()
     simple_fibonacci_time()


if __name__ == "__main__":
 main()












'''simple docstring'''



# This Python program implements an optimal binary search tree (abbreviated BST)
# building dynamic programming algorithm that delivers O(n^2) performance.
#
# The goal of the optimal BST problem is to build a low-cost BST for a
# given set of nodes, each with its own key and frequency. The frequency
# of the node is defined as how many time the node is being searched.
# The search cost of binary search tree is given by this formula:
#
# cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
#
# where n is number of nodes in the BST. The characteristic of low-cost
# BSTs is having a faster overall search time than other implementations.
# The reason for their fast search time is that the nodes with high
# frequencies will be placed near the root of the tree while the nodes
# with low frequencies will be placed near the leaves of the tree thus
# reducing search time in the most frequent instances.
import sys
from random import randint





class     lowerCAmelCase   :


       def __init__(   self    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE  )      ->  Optional[int]:



            '''simple docstring'''




            __snake_case    					=  key
            __snake_case    					=  freq




       def __str__(   self  )      ->  List[Any]:



            '''simple docstring'''




            return F'''Node(key={self.key}, freq={self.freq})'''







def 			_UpperCamelCase (_lowerCamelCase							:     str   ,	_lowerCamelCase							:     List[str]   ,	_lowerCamelCase							:     Union[str, Any]   ,	_lowerCamelCase							:     int   ,	_lowerCamelCase							:     List[Any]   ,	_lowerCamelCase							:     Tuple	)->   Any:




     '''simple docstring'''





     if i > j or i < 0 or j > len(_lowerCamelCase	) - 1:
          return

     __snake_case    					=  root[i][j]
     if parent == -1:  # root does not have a parent
          print(f'''{key[node]} is the root of the binary search tree.'''	)
     elif is_left:
          print(f'''{key[node]} is the left child of key {parent}.'''	)
     else:
          print(f'''{key[node]} is the right child of key {parent}.'''	)

     print_binary_search_tree(_lowerCamelCase   ,	_lowerCamelCase   ,	_lowerCamelCase   ,	node - 1   ,	key[node]   ,	_lowerCamelCase	)
     print_binary_search_tree(_lowerCamelCase   ,	_lowerCamelCase   ,	node + 1   ,	_lowerCamelCase   ,	key[node]   ,	_lowerCamelCase	)







def 			_UpperCamelCase (_lowerCamelCase							:     List[Any]	)->   Union[str, Any]:




     '''simple docstring'''





     nodes.sort(key=lambda _lowerCamelCase	: node.key	)

     __snake_case    					=  len(_lowerCamelCase	)

     __snake_case    					=  [nodes[i].key for i in range(_lowerCamelCase	)]
     __snake_case    					=  [nodes[i].freq for i in range(_lowerCamelCase	)]

     # This 2D array stores the overall tree cost (which's as minimized as possible);
     # for a single key, cost is equal to frequency of the key.
     __snake_case    					=  [[freqs[i] if i == j else 0 for j in range(_lowerCamelCase	)] for i in range(_lowerCamelCase	)]
     # sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
     # array
     __snake_case    					=  [[freqs[i] if i == j else 0 for j in range(_lowerCamelCase	)] for i in range(_lowerCamelCase	)]
     # stores tree roots that will be used later for constructing binary search tree
     __snake_case    					=  [[i if i == j else 0 for j in range(_lowerCamelCase	)] for i in range(_lowerCamelCase	)]

     for interval_length in range(2   ,	n + 1	):
          for i in range(n - interval_length + 1	):
               __snake_case    					=  i + interval_length - 1

               __snake_case    					=  sys.maxsize  # set the value to "infinity"
               __snake_case    					=  total[i][j - 1] + freqs[j]

               # Apply Knuth's optimization
               # Loop without optimization: for r in range(i, j + 1):
               for r in range(root[i][j - 1]   ,	root[i + 1][j] + 1	):  # r is a temporal root
                    __snake_case    					=  dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
                    __snake_case    					=  dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
                    __snake_case    					=  left + total[i][j] + right

                    if dp[i][j] > cost:
                         __snake_case    					=  cost
                         __snake_case    					=  r

     print('''Binary search tree nodes:'''	)
     for node in nodes:
          print(_lowerCamelCase	)

     print(f'''\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}.'''	)
     print_binary_search_tree(_lowerCamelCase   ,	_lowerCamelCase   ,	0   ,	n - 1   ,	-1   ,	_lowerCamelCase	)







def 			_UpperCamelCase ()->   Union[str, Any]:




     '''simple docstring'''





     __snake_case    					=  [Node(_lowerCamelCase   ,	randint(1   ,	50	)	) for i in range(10   ,	0   ,	-1	)]
     find_optimal_binary_search_tree(_lowerCamelCase	)


if __name__ == "__main__":
     main()






