Bro it’s a dp problem. Try to solve some standard dp problems and you’ll understand the question
It can be solved using dynamic programming in O(n) time but I have applied matrix exponentiation to solve it in O(log(n)) time.
def multiply(A,B):
m = len(A)
l = len(A[0])
n = len(B[0])
C = [[0 for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
for r in range(l):
C[i][j] += A[i][r] * B[r][j]
return C
def ways(n):
if n == 0:
return 1
elif n == 1:
return 2
elif n == 2:
return 4
else:
n -= 2
a = [[4],[2],[1]]
x = [[1,1,1],[1,0,0],[0,1,0]]
result = [[1,0,0],[0,1,0],[0,0,1]]
while n:
if n % 2 == 1:
result = multiply(result,x)
n >>= 1
x = multiply(x,x)
result = multiply(result,a)
return result[0][0]
t = int(input())
for i in range(t):
n = int(input())
print(ways(n))