#1059524 (PyPy3) No.1677 mæx

• 問題: No.1677 mæx
• ユーザー: lam6er
• 提出日時: 2025-03-26 15:48:53
• 言語: PyPy3 (7.3.15)
• 結果: TLE
• 実行時間: -
• コード長: 3,495 bytes
• コンパイル時間: 168 ms
• コンパイル使用メモリ: 82,744 KB
• 実行使用メモリ: 54,636 KB
• 最終ジャッジ日時: 2025-03-26 15:50:01
• 合計ジャッジ時間: 4,004 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 4
other	TLE * 1 -- * 17

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import sys
MOD = 998244353
def main():
    sys.setrecursionlimit(1 << 25)
    s = sys.stdin.readline().strip()
    K = int(sys.stdin.readline())
    class Node:
        def __init__(self):
            self.dp = [0, 0, 0]
    class DigitNode(Node):
        def __init__(self, c):
            super().__init__()
            self.c = c
            if c == '0':
                self.dp[0] = 1
            elif c == '1':
                self.dp[1] = 1
            elif c == '2':
                self.dp[2] = 1
            else:  # '?'
                self.dp = [1, 1, 1]
    class FunctionNode(Node):
        def __init__(self, possible_types, left, right):
            super().__init__()
            self.possible_types = possible_types  # list of (type, count)
            self.left = left
            self.right = right
    def parse(s):
        n = len(s)
        stack = []
        i = 0
        while i < n:
            if s[i] == 'm':
                func_char2 = s[i+1] if i+1 < n else '?'
                func_types = []
                if func_char2 == 'a':
                    func_types = [('max', 1)]
                elif func_char2 == 'e':
                    func_types = [('mex', 1)]
                elif func_char2 == '?':
                    func_types = [('max', 1), ('mex', 1)]
                i += 3  # skip 'm?x'
                # Now parse arguments inside ()
                i += 1  # skip '('
                balance = 1
                comma_pos = -1
                start = i
                while i < n:
                    if s[i] == '(':
                        balance += 1
                    elif s[i] == ')':
                        balance -= 1
                        if balance == 0:
                            break
                    elif s[i] == ',' and balance == 1 and comma_pos == -1:
                        comma_pos = i
                    i += 1
                left_str = s[start:comma_pos]
                right_str = s[comma_pos+1:i]
                # Parse left and right
                left = parse(left_str)
                right = parse(right_str)
                node = FunctionNode(func_types, left, right)
                stack.append(node)
                i += 1  # move past ')'
            elif s[i] in {'0', '1', '2', '?'}:
                node = DigitNode(s[i])
                stack.append(node)
                i += 1
            else:
                i += 1
        return stack[0] if stack else None
    root = parse(s)
    mex_table = [
        [1, 2, 1],
        [2, 0, 0],
        [1, 0, 0]
    ]
    def compute_dp(node):
        if isinstance(node, DigitNode):
            return
        if isinstance(node, FunctionNode):
            compute_dp(node.left)
            compute_dp(node.right)
            left_dp = node.left.dp
            right_dp = node.right.dp
            new_dp = [0, 0, 0]
            for func_type, count in node.possible_types:
                for a in range(3):
                    for b in range(3):
                        if func_type == 'max':
                            res = max(a, b)
                        else:
                            res = mex_table[a][b]
                        contrib = left_dp[a] * right_dp[b] % MOD
                        contrib = contrib * count % MOD
                        new_dp[res] = (new_dp[res] + contrib) % MOD
            node.dp = new_dp
    compute_dp(root)
    print(root.dp[K] % MOD if root else 0)
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX