結果

問題 No.1677 mæx
ユーザー brthyyjp
提出日時 2021-09-11 03:18:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 317 ms / 2,000 ms
コード長 1,020 bytes
コンパイル時間 694 ms
コンパイル使用メモリ 81,728 KB
実行使用メモリ 132,376 KB
最終ジャッジ日時 2024-06-13 04:00:10
合計ジャッジ時間 6,403 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**9)

s = str(input())
k = int(input())
mod = 998244353
n = len(s)

def mex(a, b):
    for i in range(3):
        if i not in (a, b):
            return i

nx = [-1]*n
stack = []
for i, c in enumerate(s):
    if c == '(':
        stack.append(i)
    elif c == ',':
        nx[stack[-1]] = i
    elif c == ')':
        stack.pop()

def rec(l, r):
    # [l, r)
    if l+1 == r:
        if s[l] == '?':
            return [1]*3
        res = [0]*3
        res[int(s[l])] = 1
        return res

    r -= 1
    l += 1
    ops = []
    if s[l] == '?':
        ops.append(max)
        ops.append(mex)
    elif s[l] == 'a':
        ops.append(max)
    elif s[l] == 'e':
        ops.append(mex)
    l += 2

    m = nx[l]
    A = rec(l+1, m)
    B = rec(m+1, r)
    res = [0]*3
    for op in ops:
        for i, a in enumerate(A):
            for j, b in enumerate(B):
                x = op(i, j)
                res[x] += a*b
                res[x] %= mod
    return res

print(rec(0, n)[k])
0