fork download
copy 
  1. def mult(a,b):
  2. 	n = len(a)
  3. 	m = len(a[0])
  4. 	l = len(b[0])
  5.  
  6. 	ans = [[0 for _ in range(l)] for __ in range(n)]
  7. 	for i in range(n):
  8. 		for j in range(l):
  9. 			calc = 0
  10. 			for k in range(m):
  11. 				calc += a[i][k]*b[k][j]
  12. 			ans[i][j] = calc
  13.  
  14. 	return ans
  15.  
  16. # Exp. rapida de matrices
  17. # Realiza O(log(n)) multiplicaciones de matrices
  18. def binexp(A,n):
  19. 	if n == 1:
  20. 		return A
  21. 	if n % 2 == 0:
  22. 		preans = binexp(A,n//2)
  23. 		return mult(preans,preans)
  24. 	preans = binexp(A,(n-1)//2)
  25. 	preans = mult(preans,preans)
  26. 	return mult(preans,A)
  27.  
  28. # Transformación
  29. A = [
  30. 	[1,0,4,0],
  31. 	[1,0,0,0],
  32. 	[0,0,1,1],
  33. 	[0,0,1,0]
  34. ]
  35.  
  36. # Matriz original
  37. # [[g(1)],[g(0)],[f(2)],[f(1)]]
  38. B = [
  39. 	[4],
  40. 	[0],
  41. 	[1],
  42. 	[1]
  43. ]
  44.  
  45. def perimeter(n):
  46. 	ans = mult(binexp(A,n),B)
  47. 	return ans[1][0]
  48.  
  49. n_testcase = int(input())
  50. for _ in range(n_testcase):
  51. 	n = int(input())
  52. 	print(perimeter(n))
Success #stdin #stdout 0.04s 9772KB
comments (?)
stdin
copy 
5
6
7
8
21
31
stdout
copy 
80
132
216
114624
14098308
https://ideone.com/bXzSD2
language:
Python 3 (python  3.9.5)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!