Chương trình đếm số cách chúng ta có thể điền vào ô 3 x n với 2 x 1 dominos trong Python

Giả sử chúng ta có một số n, chúng ta phải tìm số cách chúng ta có thể điền vào một khối (3 x n) với 1 x 2 dominos. Chúng tôi có thể xoay các dominos khi được yêu cầu. Nếu câu trả lời là rất lớn thì hãy trả về bản mod này 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =4, thì đầu ra sẽ là 11.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m =10 ^ 9 + 7
• nếu n lẻ, thì
  • trả về 0
• cs:=1, os:=0
• đối với tôi trong phạm vi từ 2 đến n, tăng thêm 2, thực hiện
  • cs:=3 * cs + os
  • hệ điều hành:=2 * cs + hệ điều hành
• trả lại cs mod m

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n % 2 == 1:
         return 0
      cs = 1
      os = 0
      for i in range(2, n + 1, 2):
         cs, os = (3 * cs + os, 2 * cs + os,)
      return cs % m
ob = Solution()
n = 4
print(ob.solve(n))

Đầu vào

4

Đầu ra

11