题目描述

总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。

给你一个整数列表的列表 hats，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。

由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。

样例

输入：hats = [[3,4],[4,5],[5]]
输出：1
解释：给定条件下只有一种方法选择帽子。
第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。

输入：hats = [[3,5,1],[3,5]]
输出：4
解释：总共有 4 种安排帽子的方法：
(3,5)，(5,3)，(1,3) 和 (1,5)

输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
输出：24
解释：每个人都可以从编号为 1 到 4 的帽子中选。
(1,2,3,4) 4 个帽子的排列方案数为 24。

输入：hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
输出：111

限制

• n == hats.length
• 1 <= n <= 10
• 1 <= hats[i].length <= 40
• 1 <= hats[i][j] <= 40
• hats[i] 包含一个数字互不相同的整数列表。

算法

(状态压缩动态规划) $O(40 n 2^n)$

1. 考虑到较小数据范围，求一个很大的方案数，应该是状压 DP。帽子的个数达到了 40，所以我们考虑状压人。
2. 设状态 $f(i, S)$ 表示考虑了前 $i$ 顶帽子，戴帽子人的集合 $S$ 的方案数。这里的帽子下标从 1 开始。
3. 初始时，$f(0, 0) = 1$，其余为 0。
4. 转移时，对于一个状态 $(i, S)$，如果不使用第 $i$ 顶帽子，则转移 $f(i, S) = f(i, S) + f(i - 1, S)$。如果使用第 $i$ 顶帽子，则需要枚举一个在集合中人 $j$ 且这个人喜欢第 $j$ 顶帽子，则转移 $f(i, S) = f(i, S) + f(i - 1, S - (1 << j))$。
5. 最终答案为 $f(40, (1 << n) - 1)$。

时间复杂度

• 状态数为 $O(40 * 2^n)$，每次有 $O(n)$ 种转移，故总时间复杂度为 $O(40 n 2^n)$。

空间复杂度

• 需要额外 $O(40 * 2^n)$ 的空间记录状态。

C++ 代码

class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        const int mod = 1000000007;
        int n = hats.size();
        vector<vector<int>> f(41, vector<int>(1 << n, 0));
        vector<vector<bool>> h(n, vector<bool>(41, false));

        for (int i = 0; i < n; i++)
            for (int j : hats[i])
                h[i][j] = true;

        f[0][0] = 1;

        for (int i = 1; i <= 40; i++)
            for (int s = 0; s < (1 << n); s++) {
                f[i][s] = (f[i][s] + f[i - 1][s]) % mod;
                for (int j = 0; j < n; j++)
                    if ((s & (1 << j)) && h[j][i])
                        f[i][s] = (f[i][s] + f[i - 1][s ^ (1 << j)]) % mod;
            }

        return f[40][(1 << n) - 1];
    }
};