Ways to Assign Distinct Hats to People
Each person lists the hats they are willing to wear, drawn from 40 hat types. Count the ways to give every person a distinct hat so no two people share the same hat.
Problem
There are 40 different hat types numbered 1..40. Given hats where hats[i] is the list of hat types person i likes, return the number of ways to assign hats so that each person wears one hat they like and no two people wear the same hat. Return the count modulo 1e9+7.
Input
An array hats of length n where hats[i] is a list of liked hat numbers (1..40).
Output
An integer: the number of valid assignments modulo 1e9+7.
Constraints
- 1 <= n <= 10
- 1 <= hats[i].length <= 40
- 1 <= hat number <= 40; lists contain no duplicates.
Examples
Example 1
Input
hats = [[3,4],[4,5],[5]]
Output
1
Person 0→3, person 1→4, person 2→5 is the only valid assignment.
Example 2
Input
hats = [[3,5,1],[3,5]]
Output
4
Four distinct ways to give the two people different liked hats.