Chương trình đếm số cách điền hộp 3×n bằng domino 2×1 trong Python

Cho số nguyên n, đếm số cách lấp đầy hình chữ nhật 3×n bằng domino 1×2 (có thể xoay). Kết quả modulo 10⁹+7.

Ví dụ: n=4 → 11 cách.

Giải thuật (Công thức truy hồi)

Chỉ có giải khi n chẵn. Đặt cs = số cách điền 3×i đầy đủ, os = số cách điền 3×i với một góc thiếu.

• Khởi tạo cs=1, os=0.
• Với i từ 2 đến n bước 2:
  • cs, os = 3*cs + os, 2*cs + os.
• Trả về cs % MOD.

Mã nguồn Python

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

ob = Solution()
n = 4
print(ob.solve(n))  # Output: 11

Đầu vào

4

Đầu ra

11