結果

問題 No.3208 Parse AND OR Affection
コンテスト
ユーザー amesyu
提出日時 2025-07-22 18:57:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,113 bytes
コンパイル時間 387 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 213,772 KB
最終ジャッジ日時 2025-07-22 18:58:10
合計ジャッジ時間 48,224 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Generated By Gemini 2.5 Pro

import sys

sys.setrecursionlimit(252525 + 5)
readline = sys.stdin.readline

def mat_mul(A, B):
    """Multiplies two 4x4 matrices."""
    C = [[0, 0, 0, 0] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                C[i][j] += A[i][k] * B[k][j]
    return C

def solve():
    try:
        N, Q = map(int, readline().split())
        X = readline().strip()
    except (IOError, ValueError):
        return

    N_prime = (N + 1) // 2
    
    # --- 1. Preprocessing: Create Transition Matrices ---
    identity_matrix = [[(1 if i == j else 0) for j in range(4)] for i in range(4)]
    matrices = [identity_matrix] * N_prime

    A = [(X[2 * i] == 'T') for i in range(N_prime)]
    op_map = {'+': 0, '*': 1, '^': 2}
    
    for q in range(N_prime): # 0-indexed operand q
        M = [[0] * 4 for _ in range(4)]
        
        # Determine coefficients based on h_{q-1} and A[q]
        # For q=0, there is no h_{q-1}, so we treat it as an identity transform
        h_T_is_T, h_F_is_T = True, False
        if q > 0:
            op = op_map[X[2 * q - 1]]
            if op == 0:   # OR
                h_T_is_T, h_F_is_T = (True, True) if A[q] else (True, False)
            elif op == 1: # AND
                h_T_is_T, h_F_is_T = (True, False) if A[q] else (False, False)
            else: # XOR
                h_T_is_T, h_F_is_T = (False, True) if A[q] else (True, False)
        
        a = 1 if h_T_is_T else 0
        b = 1 if h_F_is_T else 0
        d = 1 - a
        e = 1 - b
        c = 1 if A[q] else 0
        g = 1 - c

        # V_q = V_{q-1} * M_q, where V = [num_F, num_T, const_1, total_T]
        M[0][0], M[0][1] = e, b
        M[1][0], M[1][1] = d, a
        M[2][0], M[2][1], M[2][2] = g, c, 1
        M[3][3] = 1
        
        # total_T column
        M[0][3] = b
        M[1][3] = a
        M[2][3] = c
        
        matrices[q] = M
        
    # --- 2. Build Segment Tree ---
    seg_tree = [identity_matrix] * (2 * N_prime)
    for i in range(N_prime):
        seg_tree[N_prime + i] = matrices[i]
    for i in range(N_prime - 1, 0, -1):
        # Note the order of multiplication for V*M1*M2 = V*(M1*M2)
        seg_tree[i] = mat_mul(seg_tree[2 * i], seg_tree[2 * i + 1])
        
    # --- 3. Process Queries ---
    for _ in range(Q):
        L, R = map(int, readline().split())
        l_idx, r_idx = (L - 1) // 2, (R - 1) // 2
        
        res_matrix = identity_matrix
        l, r = l_idx + N_prime, r_idx + N_prime + 1
        while l < r:
            if l & 1:
                res_matrix = mat_mul(res_matrix, seg_tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_matrix = mat_mul(res_matrix, seg_tree[r])
            l >>= 1
            r >>= 1
            
        # The initial vector is [0, 0, 1, 0] for a subproblem
        # [num_F, num_T, const_1, total_T]
        # The result is [0,0,1,0] * res_matrix, which is the 3rd row (index 2)
        print(res_matrix[2][3] + res_matrix[2][1])

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