黑白方格画

难度: Easy

小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 `n * n` 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色（选择的整行、整列均需涂成黑色），所选行数、列数均可为 0。小扣希望最终的成品上需要有 `k` 个黑色格子，请返回小扣共有多少种涂色方案。注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。 **示例 1：** >输入：`n = 2, k = 2` > >输出：`4` > >解释：一共有四种不同的方案： >第一种方案：涂第一列； >第二种方案：涂第二列； >第三种方案：涂第一行； >第四种方案：涂第二行。 **示例 2：** >输入：`n = 2, k = 1` > >输出：`0` > >解释：不可行，因为第一次涂色至少会涂两个黑格。 **示例 3：** >输入：`n = 2, k = 4` > >输出：`1` > >解释：共有 2*2=4 个格子，仅有一种涂色方案。 **限制：** - `1 <= n <= 6` - `0 <= k <= n * n`

Submission

运行时间: 22 ms

内存: 16.0 MB

class Solution:
    def paintingPlan(self, n: int, k: int) -> int:
        def comb(n, m):
            a = 1
            for t in range(m+1,n+1):
                a *= t 
            b = 1
            for t in range(1,n-m+1):
                b *= t
            return a // b 
        if(k == n*n):
            return 1
        result = 0
        for x in range(n):
            if(k-n*x<0):
                break
            if (k-n*x)%(n-x) == 0:
                y = (k-n*x)//(n-x)
                result += comb(n,x)*comb(n,y)
        return result

Explain

题解的思路基于组合计算和条件筛选。首先，如果需要涂的格子数k等于n*n，即整个画板全部涂黑，那么只有一种方案。否则，通过枚举涂黑的行数x和列数y，来计算符合条件的涂色方案数。对于给定的行数x，计算需要涂黑的列数y，满足条件k = nx + (n-x)y（因为涂黑x行后，剩余需要涂黑的格子数为k-n*x，这些格子必须通过涂y列得到，但要减去已经被涂黑的x行和y列重合的部分）。如果(k-n*x)可以整除(n-x)，则y是一个合法的列数，计算这种情况的方案数。方案数由组合数计算得出，即选择x行的组合数乘以选择y列的组合数。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def paintingPlan(self, n: int, k: int) -> int:
        # 组合数计算函数
        def comb(n, m):
            a = 1
            # 计算分子
            for t in range(m+1, n+1):
                a *= t
            b = 1
            # 计算分母
            for t in range(1, n-m+1):
                b *= t
            return a // b
        # 如果需要的黑色格子数为全板，则返回1
        if k == n * n:
            return 1
        result = 0
        # 枚举可能的涂黑行数x
        for x in range(n):
            # 如果剩余需涂黑的格子数小于0，则终止循环
            if k - n * x < 0:
                break
            # 检查能否整除，即是否可以完全通过涂y列来满足剩余黑格数
            if (k - n * x) % (n - x) == 0:
                y = (k - n * x) // (n - x)
                # 累加符合条件的方案数
                result += comb(n, x) * comb(n, y)
        return result

Explore

这个公式基于总涂黑格子数的分布逻辑。当你决定涂黑x行时，已经涂黑了x*n个格子。如果还需要涂黑k个格子，剩余需涂黑的格子数为k - n*x。这些剩余的格子需要通过涂色列数y来完成，但涂色的行和列会在交叉点重复计算。因此，剩余的涂色列数y应该满足条件k - n*x = y*(n - x)，即剩余的格子数等于y乘以除了已经涂黑的x行之外的其他行。整理后得到y = (k - n * x) / (n - x)。

如果`k - n * x`小于0，意味着当涂黑了x行后，剩余需要涂黑的格子数为负数，这是不可能的情况。因为你不能有负数的格子需要涂黑，这表明已经超过了需要涂黑的总数k。由于x在增加的过程中，n * x也在增加，这会使剩余需涂黑的格子数进一步减少，所以一旦这个值变为负数，对于更大的x值，这个差值只会更小（更负）。因此，没有必要继续增加x的值并尝试计算。

在题解中提供的`comb(n, m)`函数仅计算了基本的组合数，没有显式地处理当`m > n`的情况，即理论上应该返回0的情况。然而，在实际应用中，函数的调用是在确定`m`和`n`的值是合理的情况下进行的。如果需要增强函数的健壮性和通用性，应当在函数内部加入对`m > n`情况的检查，并在这种情况下返回0。