Chương trình đếm số cách cắt ma trận thành k phần trong Python

Cho ma trận nhị phân và giá trị k. Cần chia ma trận thành k phần, mỗi phần chứa ít nhất một 1. Quy tắc cắt:

1. Chọn hướng: dọc (vertical) hoặc ngang (horizontal)
2. Chọn chỉ số cắt ma trận thành 2 phần
3. Cắt dọc: không thể cắt phần trái, chỉ tiếp tục cắt phần phải
4. Cắt ngang: không thể cắt phần trên, chỉ tiếp tục cắt phần dưới

Tìm số cách chia khác nhau. Kết quả modulo 10⁹+7.

Ví dụ: ma trận 3×3, k=2 → output 4 (cắt dọc 2 cách, cắt ngang 2 cách).

Thuật toán DP + Prefix Sum:

• Tính counts[i,j] = số lượng 1 trong submatrix từ (i,j) đến (m-1,n-1) (bottom-right)
• Công thức: counts[i,j] = counts[i+1,j] + counts[i,j+1] - counts[i+1,j+1] + matrix[i,j]
• Hàm đệ quy f(x, y, c): số cách cắt submatrix từ (x,y) thành c+1 phần
• Base case: c==0 → return 1 nếu count>0 else 0
• Thử cắt ngang: duyệt i từ x+1 đến m-1, nếu 0 < counts[i,y] < count → ans += f(i, y, c-1)
• Thử cắt dọc: duyệt j từ y+1 đến n-1, nếu 0 < counts[x,j] < count → ans += f(x, j, c-1)
• Return ans % MOD

Triển khai

from collections import defaultdict

class Solution:
    def solve(self, matrix, k):
        MOD = 10**9 + 7
        m, n = len(matrix), len(matrix[0])
        counts = defaultdict(int)
        
        # Prefix sum bottom-right
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                counts[(i, j)] = (counts[(i+1, j)] + counts[(i, j+1)] 
                                 - counts[(i+1, j+1)] + matrix[i][j])
        
        def f(x, y, c):
            count = counts[(x, y)]
            if c == 0:
                return 1 if count > 0 else 0
            ans = 0
            # Cắt ngang
            for i in range(x+1, m):
                if 0 < counts[(i, y)] < count:
                    ans += f(i, y, c-1)
            # Cắt dọc
            for j in range(y+1, n):
                if 0 < counts[(x, j)] < count:
                    ans += f(x, j, c-1)
            return ans % MOD
        
        return f(0, 0, k-1)

ob = Solution()
matrix = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
k = 2
print(ob.solve(matrix, k))

Đầu vào

[[1, 1, 0], [1, 0, 1], [1, 1, 1]], 2

Đầu ra

4

Lưu ý: Có thể tối ưu bằng memoization (lru_cache) cho hàm f(x,y,c) vì có overlapping subproblems.