#1059656 (PyPy3) No.1239 Multiplication -2

• 問題: No.1239 Multiplication -2
• ユーザー: lam6er
• 提出日時: 2025-03-26 15:57:02
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 195 ms / 2,000 ms
• コード長: 3,276 bytes
• コンパイル時間: 388 ms
• コンパイル使用メモリ: 81,920 KB
• 実行使用メモリ: 138,272 KB
• 最終ジャッジ日時: 2025-03-26 15:57:31
• 合計ジャッジ時間: 5,762 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 34

ソースコード

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
113
import sys
MOD = 998244353
def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    a = list(map(int, input[1:N+1]))
    
    max_n = 2 * 10**5 + 10
    pow2 = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        pow2[i] = (pow2[i-1] * 2) % MOD
    inv2 = pow(2, MOD-2, MOD)
    inv_pow2 = [1] * (max_n + 1)
    inv_pow2[1] = inv2
    for i in range(2, max_n + 1):
        inv_pow2[i] = (inv_pow2[i-1] * inv2) % MOD
    
    runs = []
    current_run = []
    start = 0
    for i in range(N):
        if a[i] != 0:
            if not current_run:
                start = i
            current_run.append(a[i])
        else:
            if current_run:
                runs.append( (start, i-1, current_run) )
                current_run = []
    if current_run:
        runs.append( (start, N-1, current_run) )
    
    total = 0
    for (l, r, elements) in runs:
        m = len(elements)
        pos_list = []
        for idx in range(m):
            if abs(elements[idx]) == 2:
                pos_list.append(idx + 1)
        if not pos_list:
            continue
        
        prefix_parity = [0] * (m + 1)
        cnt = 0
        for i in range(m):
            if elements[i] < 0:
                cnt += 1
            prefix_parity[i+1] = cnt % 2
        
        sum0 = [0] * (m + 1)
        sum1 = [0] * (m + 1)
        run_start = l + 1
        for s in range(1, m + 1):
            if run_start >= 2:
                val = pow2[s-1]
            else:
                if s == 1:
                    val = 2 % MOD
                else:
                    val = pow2[s-1] % MOD
            parity = prefix_parity[s-1]
            sum0[s] = sum0[s-1]
            sum1[s] = sum1[s-1]
            if parity == 0:
                sum0[s] = (sum0[s] + val) % MOD
            else:
                sum1[s] = (sum1[s] + val) % MOD
        
        t = len(pos_list)
        for i in range(t):
            pos = pos_list[i]
            prev_pos = pos_list[i-1] if i > 0 else None
            next_pos = pos_list[i+1] if i < t -1 else None
            
            L = 1
            if prev_pos is not None:
                L = prev_pos + 1
            R = m
            if next_pos is not None:
                R = next_pos - 1
            
            for e in range(pos, R + 1):
                parity_e = prefix_parity[e]
                desired_parity = 1 - parity_e
                a_s = L
                b_s = pos
                sum_val = 0
                if a_s > b_s:
                    continue
                if desired_parity == 0:
                    sum_val = (sum0[b_s] - sum0[a_s - 1]) % MOD
                else:
                    sum_val = (sum1[b_s] - sum1[a_s - 1]) % MOD
                
                if sum_val < 0:
                    sum_val += MOD
                
                if r < N - 1:
                    pow_term = e + 1
                else:
                    if e < m:
                        pow_term = e + 1
                    else:
                        pow_term = e
                
                inv = inv_pow2[pow_term]
                contribution = (sum_val * inv) % MOD
                total = (total + contribution) % MOD
    print(total % MOD)
if __name__ == '__main__':
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX