1434. Number of Ways to Wear Different Hats to Each Other¶
题目信息¶
- 题号:
1434
- 难度:
Hard
- 主题:
状态压缩、动态规划、二分图匹配计数
- 原题:
- 重点:
每个人选择一顶自己喜欢的帽子,所有人帽子编号必须互不相同;统计分配方案并取模
题目重述¶
有 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
解释:同一顶帽子不能同时分配给两人。