题目描述

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

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

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

样例

输入：n = 2, k = 2
输出：4
解释：一共有四种不同的方案：
第一种方案：涂第一列；
第二种方案：涂第二列；
第三种方案：涂第一行；
第四种方案：涂第二行。

输入：n = 2, k = 1
输出：0
解释：不可行，因为第一次涂色至少会涂两个黑格。

输入：n = 2, k = 4
输出：1
解释：共有 2*2=4 个格子，仅有一种涂色方案。

限制

• 1 <= n <= 6
• 0 <= k <= n * n

算法1

(暴力枚举) $O(n^2 \cdot 2^{2n})$

1. 暴力枚举每一行每一列的组合，使用二进制的方式记录每个格子的情况，并将每个符合条件的情况记录到哈希表中避免重复。

时间复杂度

• 共有 $O(2^{2n})$ 种组合，每种组合需要 $O(n^2)$ 的时间判断。
• 故总时间复杂度为 $O(n^2 \cdot 2^{2n})$。

空间复杂度

• 需要 $O(2^{2n})$ 的空间存储哈希表。

C++ 代码

#define LL long long

class Solution {
public:
    int paintingPlan(int n, int k) {
        int ans = 0;

        unordered_set<LL> seen;

        for (int w = 0; w < (1 << n); w++)
            for (int h = 0; h < (1 << n); h++) {

                LL s = 0;
                for (int i = 0; i < n; i++)
                    if ((w >> i) & 1)
                        for (int j = 0; j < n; j++)
                            s |= 1ll << (i * n + j);

                for (int j = 0; j < n; j++)
                    if ((h >> j) & 1)
                        for (int i = 0; i < n; i++)
                            s |= 1ll << (i * n + j);

                int tot = 0;
                for (int i = 0; i < n * n; i++)
                    if ((s >> i) & 1)
                        tot++;

                if (tot == k && seen.find(s) == seen.end())
                    ans++;

                seen.insert(s);
            }

        return ans;
    }
};

算法2

(暴力枚举) $O(n \cdot 2^n)$

1. 只枚举行的情况，列的情况可以通过计算排列组合得出。

时间复杂度

• 行共有 $O(2^n)$ 种组合，每次需要 $O(n)$ 的时间计算，故总时间复杂度为 $O(n \cdot 2^n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储阶乘数组。

C++ 代码

class Solution {
public:
    int paintingPlan(int n, int k) {
        if (k == n * n)
            return 1;

        int ans = 0;
        vector<int> fact(n + 1);
        fact[0] = 1;
        for (int i = 1; i <= n; i++)
            fact[i] = fact[i - 1] * i;

        for (int w = 0; w < (1 << n) - 1; w++) {
            int s = 0;
            for (int i = 0; i < n; i++)
                if ((w >> i) & 1)
                    s++;

            if (s * n > k)
                continue;

            int r = k - s * n;
            if (r % (n - s) != 0)
                continue;

            int h = r / (n - s);
            ans += fact[n] / fact[h] / fact[n - h];
        }
        return ans;
    }
};

算法3

(枚举) $O(n^2)$

1. 枚举涂黑的行数和列数 $i$ 和 $j$。
2. 如果 $(i + j)n - ij = k$，则通过组合数计算选择 $i$ 行和 $j$ 的情况总和。
3. 注意，行数 $i$ 和列数 $j$ 需要小于 $n$。这是因为等于 $n$ 时仅有一种全黑的情况，此时需要直接特判否则会出现重复。

时间复杂度

• 行共有 $O(2^n)$ 种组合，每次需要 $O(n)$ 的时间计算，故总时间复杂度为 $O(n \cdot 2^n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储阶乘数组。

C++ 代码

class Solution {
public:
    int paintingPlan(int n, int k) {
        if (n * n == k)
            return 1;

        vector<vector<int>> C(n + 1, vector<int>(n + 1, 0));
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++)
                C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if ((i + j) * n - i * j == k)
                    ans += C[n][i] * C[n][j];

        return ans;
    }
};