标签: 数学
难度: Easy
标签: 数学
难度: Easy
运行时间: 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
题解的思路基于组合计算和条件筛选。首先,如果需要涂的格子数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
这个公式基于总涂黑格子数的分布逻辑。当你决定涂黑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。