每个人戴不同帽子

---

image.png

i表示帽子1->40，j代表二进制下人的状态，dp[i][j]代表帽子i对应的人的分配状态j下的解个数，最终的结果是最后顶帽子确定是否戴且所有人都有帽子情况下的解个数dp[-1][-1]

dp[i][j]可以选择不戴帽子i=dp[i-1][j]，可以选择人k戴帽子i=dp[i][j-(1<<k)]

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        hat2people=[[] for i in range(41)]
        hatslen=(1<<(len(hats)))
        dp = [[0] * hatslen for i in range(41)]
        for i in range(len(hats)):
            for j in hats[i]:
                hat2people[j].append(i)
        dp[0][0]=1
        mod=10**9+7

        for i in range(1,41):
            for j in range(hatslen):
                dp[i][j]=dp[i-1][j]
                for k in hat2people[i]:
                    if(j&(1<<k)>0):
                        dp[i][j]+=dp[i-1][j-(1<<k)]
                dp[i][j]%=mod
                print(i,j,dp[i][j])
        return dp[-1][-1]