โปรแกรมนับจำนวนวิธีวางโดมิโน 2x1 ในกล่อง 3xn ใน Python

สมมติว่าเรามีตัวเลข n ต้องการหาจำนวนวิธีเติมกล่องขนาด 3 x n ด้วยโดมิโนขนาด 1 x 2 (หมุนได้) ถ้าคำตอบมากเกินไป modulo 10^9+7

เช่น n = 4 ผลลัพธ์ = 11

ขั้นตอนการแก้ปัญหา (Recurrence Relation)

• m = 10^9 + 7
• ถ้า n เป็นคี่ คืน 0 (ไม่สามารถเติมได้)
• cs := 1 (complete states), os := 0 (open states)
• วน i = 2..n ก้าว 2:
  • cs, os = (3*cs + os) % m, (2*cs + os) % m
• คืน cs % m

ความสัมพันธ์เวียนเกิด: f(n) = 4*f(n-2) - f(n-4) สำหรับ 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))

ข้อมูลนำเข้า

4

ผลลัพธ์

11