Участник:Nik7/Number of Ways to Wear Different Hats to Each Other
Материал из DISCOPAL
«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]