leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

总共有 n 个人和 40 种不同的帽子,帽子编号从 140

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

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

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

 

示例 1:

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

示例 2:

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

示例 3:

输入: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 。

 

提示:

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] 包含一个数字互不相同的整数列表。
通过次数
6.1K
提交次数
11.4K
通过率
53.7%


相关企业

提示 1
Dynamic programming + bitmask.

提示 2
dp(peopleMask, idHat) number of ways to wear different hats given a bitmask (people visited) and used hats from 1 to idHat-1.

相似题目

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
hats =
[[3,4],[4,5],[5]]
Source