1434. Number of Ways to Wear Different Hats to Each Other

题目信息

题号:

1434

难度:

Hard

主题:

状态压缩、动态规划、二分图匹配计数

原题:

LeetCode 1434

重点:

每个人选择一顶自己喜欢的帽子,所有人帽子编号必须互不相同;统计分配方案并取模

题目重述

有 n 个人,hats[i] 列出第 i 个人愿意佩戴的帽子编号,帽子编号位于 1 到 40。

为每个人恰好分配一顶喜欢的帽子,并要求不同人不能佩戴相同编号的帽子。请返回所有合法分配方案数量对 10^9 + 7 取模后的结果。

1 <= n <= 10,每个人的喜欢列表非空且内部编号互不相同。

自建示例

共享帽子需要分配给至多一人:

输入:hats = [[1,2],[2,3]]
输出:3
解释:合法分配为 (1,2)、(1,3) 和 (2,3),括号中依次表示两人的帽子。

所有人只喜欢同一顶帽子时无解:

输入:hats = [[1],[1]]
输出:0
解释:同一顶帽子不能同时分配给两人。