Giving Out Hats Nobody Shares
There are h kinds of hat, numbered 1 to h. Each of n people lists the hats they are
willing to wear. Give every person exactly one hat from their own list, with no two people
receiving the same hat.
Print the number of ways, modulo 1000000007.
2 people, one likes hats 3 and 4, the other 4 and 5 -> 3
2 people, both like only hat 1 -> 0
## Index by the scarce side
The natural state is a mask over the HATS, saying which have been given away. With h up to
40 that is 2^40 entries and the problem is over before it starts.
Turn it round. There are at most 10 people, so make the mask a set of PEOPLE, and walk the hats one at a time on the outside:
dp[hat][mask] = the number of ways to satisfy exactly the people in mask
using only hats 1 .. hat
Choosing which side of a bipartite problem carries the mask is the entire decision here, and the rule is simple: the mask goes on whichever side is small.
## The recurrence
Hat hat is either given to nobody, or to exactly one person who wants it:
dp[hat][mask] = dp[hat-1][mask]
+ sum over i in mask who wants hat of dp[hat-1][mask without i]
Only one person can wear a given hat, which is why the sum takes a single i rather than a
subset.
The answer is dp[h][full].
## The lookup that makes it fast
Iterating over all n people for each hat and testing membership is fine at these sizes, but
the cleaner form inverts the lists once at read time:
wants[hat] = the list of people who would wear it
Then each hat touches only the people who actually named it.
## Rolling the layer
dp[hat] depends only on dp[hat-1], so keep two arrays of 2^n and swap. Writing into the
same array in place is wrong here: a person could be served twice by the same hat, because the
half-updated row would be read as if it were the previous one.
That is the same in-place hazard as the 0/1 knapsack, and the fix is the same: either use two layers, or order the loop so nothing half-written is read.
## Boundaries
Two people who both want only hat 1 answer 0. One person with one hat answers 1.
Two people who both accept all of hats 1 to 4 answer 12, which is 4 * 3: every ordered choice
of two distinct hats.
## Cost
Time O(h * 2^n) plus the work of the per-hat lists. Space O(2^n).