Hints — p80 Number of Ways to Wear Different Hats

Hint 1. Naive bitmask on hats = 2^40 states. Infeasible. What’s special about the input? n ≤ 10 people. Flip the subject: bitmask on PEOPLE (2^10 = 1024) instead.

Hint 2. Iterate hats OUTER (1..40), people-mask INNER (0..2^n-1). Why outer hats? Each hat is “use or skip” — no need to track which hats are used; only track which people are satisfied.

Hint 3. Precompute liked_by[hat] = list of people who like that hat. Built in one pass over hats.

Hint 4. dp[h][mask] = ways using hats 1..h to satisfy exactly the people in mask. Transition: skip hat h (+= dp[h-1][mask]); or for each person p in liked_by[h] AND in mask: += dp[h-1][mask ^ (1<<p)].

Hint 5. Mod 1e9+7 every addition. Answer: dp[40][(1<<n) - 1]. Total ops: 40 × 1024 × 10 ≈ 410K. Fast.

If stuck: see solution.py.