สมมติว่าเรามีตัวเลข n เราต้องหาจำนวนวิธีที่เราสามารถเติมบล็อก (3 x n) ที่มีโดมิโน 1 x 2 ได้ เราสามารถหมุนโดมิโนได้เมื่อจำเป็น หากคำตอบมีขนาดใหญ่มาก ให้ส่งคืน mod นี้ 10^9 + 7
ดังนั้น หากอินพุตเท่ากับ n =4 เอาต์พุตจะเป็น 11
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ม =10^9 + 7
- ถ้า n เป็นเลขคี่
- คืน 0
- cs :=1, os :=0
- สำหรับฉันในช่วง 2 ถึง n เพิ่มขึ้น 2 ทำ
- cs :=3 * cs + os
- os :=2 * cs + os
- คืนค่า cs mod m
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
