【LeetCode】LCP 22. 黑白方格画

题目

小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色，所选行数、列数均可为 0。

小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。

注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ccw6C7
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

可以选择任意多行或者多列，假设选择i行和j列，那么 涂成黑色的格子 有num = （i + j) * n。考虑到行列之间有重叠的格子，因此需要减去重叠的格子数 i * j。
因此 num = (i + j) * n - (i * j)。

如 num == k，那么可能方案就是从n行中选i行、n列中选j列。因此方案数是一个组合数问题，c(n, i) * c(n, j)。

求组合数代码（这里可以优化）：

def numberCombinations(n, m):
    """
    C(n, m)
    n >= m
    """
    return math.factorial(n) // (math.factorial(n - m) * math.factorial(m))

class Solution:
    import math
    def numberCombinations(self, n, m):
        """
        C(n, m)
        n >= m
        """
        return math.factorial(n) // (math.factorial(n - m) * math.factorial(m))
    def paintingPlan(self, n: int, k: int) -> int:
        if k % n != 0 and k < n:
            return 0
        if k == n * n:
            return 1
        ans = 0
        for i in range(n + 1):
            for j in range(n + 1):
                if (i + j) * n - i * j == k:
                    # 计算组合数
                    print(i, j)
                    ans += self.numberCombinations(n, i) * self.numberCombinations(n, j)
        return ans