結果

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

ソースコード

diff # 

import sys
from collections import deque
from itertools import combinations
from sys import stdin

MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(stdin.readline().strip())
    S = list(map(int, stdin.readline().strip().split()))
    initial = {}
    for num in S:
        if num in initial:
            initial[num] += 1
        else:
            initial[num] = 1

    def get_mex(subset):
        s = set(subset)
        mex = 0
        while mex in s:
            mex += 1
        return mex

    visited = set()
    q = deque()
    q.append(initial)
    visited.add(frozenset(initial.items()))
    count = 0

    while q:
        current = q.popleft()
        count += 1

        elements = list(current.keys())
        present = {}
        for num in elements:
            present[num] = current[num]

        items = list(present.items())
        n = len(items)
        for L in range(1, n+1):
            for indices in combinations(range(n), L):
                subset_nums = []
                for i in indices:
                    num, cnt = items[i]
                    subset_nums.append(num)
                subset = subset_nums
                mex = get_mex(subset)

                new_state = {}
                for num in elements:
                    new_state[num] = current[num]
                for num in subset:
                    new_state[num] -= 1
                    if new_state[num] == 0:
                        del new_state[num]
                if mex in new_state:
                    new_state[mex] += 1
                else:
                    new_state[mex] = 1

                new_state_frozen = frozenset(new_state.items())
                if new_state_frozen not in visited:
                    visited.add(new_state_frozen)
                    q.append(new_state)

    print(count % MOD)

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