結果

問題 No.1677 mæx
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:08:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 302 ms / 2,000 ms
コード長 2,763 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 81,900 KB
実行使用メモリ 107,388 KB
最終ジャッジ日時 2025-04-15 22:09:39
合計ジャッジ時間 5,610 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

S = input().strip()
K = int(input())

from collections import defaultdict

stack = []
current_context = defaultdict(int)

i = 0
n = len(S)
while i < n:
    if S[i] == 'm' and i + 2 < n and S[i+2] == 'x':
        # Parse function name
        func_char = S[i+1]
        func_types = []
        if func_char == 'a':
            func_types.append(('max', 1))
        elif func_char == 'e':
            func_types.append(('mex', 1))
        elif func_char == '?':
            func_types.append(('max', 1))
            func_types.append(('mex', 1))
        # Push to stack
        stack.append({
            'parent_context': current_context.copy(),
            'func_types': func_types,
            'arg1_counts': None,
            'state': 'arg1'
        })
        current_context = defaultdict(int)
        i += 3
        # Skip '('
        if i < n and S[i] == '(':
            i += 1
    elif S[i] in ['0', '1', '2', '?']:
        # Parse digit
        c = S[i]
        if c == '?':
            for v in [0, 1, 2]:
                current_context[v] = (current_context[v] + 1) % MOD
        else:
            v = int(c)
            current_context[v] = (current_context[v] + 1) % MOD
        i += 1
    elif S[i] == ',':
        # Finish arg1
        if stack:
            top = stack[-1]
            if top['state'] == 'arg1':
                top['arg1_counts'] = current_context.copy()
                top['state'] = 'arg2'
                current_context = defaultdict(int)
        i += 1
    elif S[i] == ')':
        # Finish arg2
        if stack:
            top = stack.pop()
            arg2_counts = current_context.copy()
            arg1_counts = top['arg1_counts']
            parent_context = top['parent_context']
            new_counts = defaultdict(int)
            for func_type, ways in top['func_types']:
                for v1 in arg1_counts:
                    for v2 in arg2_counts:
                        cnt = (arg1_counts[v1] * arg2_counts[v2]) % MOD
                        cnt = (cnt * ways) % MOD
                        if func_type == 'max':
                            res = max(v1, v2)
                        else:
                            mex = 0
                            while mex in {v1, v2}:
                                mex += 1
                            res = mex
                        new_counts[res] = (new_counts[res] + cnt) % MOD
            # Merge new_counts into parent_context
            current_context = parent_context
            for v in new_counts:
                current_context[v] = (current_context[v] + new_counts[v]) % MOD
        i += 1
    else:
        # Skip other characters like '(', 'x', etc.
        i += 1

answer = current_context.get(K, 0) % MOD
print(answer)
0