Участник:Nik7/Number of Ways to Wear Different Hats to Each Other

Материал из DISCOPAL
< Участник:Nik7
Версия от 18:53, 4 ноября 2020; Nik7 (обсуждение | вклад) (Новая страница: «{{leetcode|number-of-ways-to-wear-different-hats-to-each-other|Number of Ways to Wear Different Hats to Each Other|}} <code-python> from collections import defaul…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

«Number of Ways to Wear Different Hats to Each Other»

from collections import defaultdict
 
class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        modulo = 1_000_000_007
        h2p = defaultdict(list)
        for i, hat in enumerate(hats):
            for h in hat:
                h2p[h].append(i)
        n = len(hats)
 
        dp, ndp = defaultdict(int), defaultdict(int)
 
        for hat in range(0, 41):
            for mask in range(1<<n):
                if mask == 0:
                    ndp[mask] = 1
                else:
                    ndp[mask] = dp[mask]
                    for p in h2p[hat]:
                        if mask & (1<<p):
                            ndp[mask] += dp[mask ^ (1<<p)]
                            ndp[mask] %= modulo
            dp, ndp = ndp, defaultdict(int)
 
        return dp[(1<<n)-1]