สมมติว่าเรามีเมทริกซ์ไบนารี N x N โดยที่ 0 สำหรับเซลล์ว่างและ 1 คือเซลล์ที่ถูกบล็อก เราต้องหาจำนวนวิธีในการเลือกเซลล์ว่าง N เซลล์ เพื่อให้ทุกแถวและทุกคอลัมน์มีเซลล์ที่เลือกอย่างน้อยหนึ่งเซลล์ หากคำตอบคือผลลัพธ์ที่ใหญ่มาก mod 10^9 + 7
ดังนั้นหากอินพุตเป็นแบบ
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากเรามีการกำหนดค่าต่อไปนี้ (โดยที่ x คือเซลล์ที่เลือก) -
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของเมทริกซ์
- กำหนดฟังก์ชัน f() นี่จะใช้เวลา i, bs
- ถ้าฉัน>=n แล้ว
- คืน 1
- ตอบ :=0
- สำหรับ j ในช่วง 0 ถึง n ทำ
- ถ้า matrix[i, j] เหมือนกับ 0 และ (2^j AND bs เหมือนกับ 0) แล้ว
- ans :=ans + f(i + 1, bs OR 2^j)
- ถ้า matrix[i, j] เหมือนกับ 0 และ (2^j AND bs เหมือนกับ 0) แล้ว
- คืนสินค้า
- จากการเรียกเมธอดหลักและคืนค่า f(0, 0)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, matrix): n = len(matrix) def f(i, bs): if i >= n: return 1 ans = 0 for j in range(n): if matrix[i][j] == 0 and ((1 << j) & bs == 0): ans += f(i + 1, bs | (1 << j)) return ans return f(0, 0) ob = Solution() matrix = [ [0, 0, 0], [0, 0, 0], [0, 1, 0] ] print(ob.solve(matrix))
อินพุต
[ [0, 0, 0], [0, 0, 0], [0, 1, 0] ]
ผลลัพธ์
4
