結果

問題 No.1963 Subset Mex
ユーザー gew1fw
提出日時 2025-06-12 20:49:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,632 bytes
コンパイル時間 166 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 84,680 KB
最終ジャッジ日時 2025-06-12 20:51:05
合計ジャッジ時間 7,967 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 998244353

def main():
    N = int(sys.stdin.readline())
    S = list(map(int, sys.stdin.readline().split()))
    
    from collections import defaultdict
    initial = defaultdict(int)
    for x in S:
        initial[x] += 1
    
    # Each state is a dictionary: key is the number, value is the count
    visited = set()
    queue = deque()
    
    # Convert the initial state to a tuple of sorted items for hashing
    initial_tuple = tuple(sorted(initial.items()))
    visited.add(initial_tuple)
    queue.append(initial_tuple)
    
    count = 0
    
    while queue:
        current = queue.popleft()
        count += 1
        
        # Convert back to a dictionary for manipulation
        current_dict = dict(current)
        
        # Generate all possible subsets (non-empty)
        # To do this, we consider each element and how many times it can be taken
        # This part is tricky because the multiset allows multiple instances
        # But for mex calculation, the presence or absence matters, not the count
        # So, for each element, we can choose to include it or not in the subset, regardless of count
        # But the subset must be non-empty
        
        # We can generate all possible subsets by considering each element's presence
        # For each number in current_dict, we can choose to include it or not
        # But we need to avoid the empty subset
        
        # Generate all possible subsets (non-empty)
        elements = list(current_dict.keys())
        n = len(elements)
        for mask in range(1, 1 << n):
            subset = []
            for i in range(n):
                if (mask >> i) & 1:
                    subset.append(elements[i])
            
            # Compute mex of subset
            mex = 0
            present = set(subset)
            while mex in present:
                mex += 1
            
            # Create the next state
            next_dict = current_dict.copy()
            for num in subset:
                if next_dict[num] > 0:
                    next_dict[num] -= 1
                    if next_dict[num] == 0:
                        del next_dict[num]
            if mex in next_dict:
                next_dict[mex] += 1
            else:
                next_dict[mex] = 1
            
            # Convert to a tuple for hashing
            next_tuple = tuple(sorted(next_dict.items()))
            if next_tuple not in visited:
                visited.add(next_tuple)
                queue.append(next_tuple)
    
    print(count % MOD)

if __name__ == '__main__':
    main()
0