数学

方法一数学

由题意可知，如果我们涂了row行，colum列，那么涂黑的格子数就是 (row + colum) * n - (row * colum)，这个题就转换成了，n行中找到row行，n列中找到colum列的可能种类。转换成排列组合其实就是
LCP 22. 黑白方格画 - 图1
根据排列组合的知识 LCP 22. 黑白方格画 - 图2

参考代码

  1. class Solution:
  2.     def paintingPlan(self, n: int, k: int) -> int:
  3.         if k == n * n:
  4.             return 1
  5.         if k > n * n:
  6.             return 0
  8.         muls = [1]
  9.         mul = 1
  10.         for i in range(1,7):
  11.             mul = i * mul
  12.             muls.append(mul)
  14.         ans = 0
  15.         for row in range(0,n):
  16.             for colum in range(0,n):
  17.                 grid = (row + colum) * n - (row * colum)
  18.                 if grid == k:
  19.                     ans += muls[n] // (muls[n-row] * muls[row]) * muls[n] // (muls[colum] * muls[n - colum])
  20.         return ans

复杂度分析

数件复杂度O(n^2)
空间复杂度O(n)