結果

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

ソースコード

diff # 

# 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):
            # This is vector-matrix multiplication V*M, so loop k on column of A / row of B
            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 Start and Transition Matrices ---
    identity_matrix = [[(1 if i == j else 0) for j in range(4)] for i in range(4)]
    start_matrices = [identity_matrix] * N_prime
    trans_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
        # Create Start Matrix S_q
        c = 1 if A[q] else 0
        f = 1 - c
        start_matrices[q] = [[0,0,0,0], [0,0,0,0], [0,0,0,0], [c,f,c,1]]

        # Create Transition Matrix T_q (for transition from q-1 to q)
        if q > 0:
            op = op_map[X[2 * q - 1]]
            h_T_is_T, h_F_is_T = False, False
            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
            
            trans_matrices[q] = [[a,d,a,0], [b,e,b,0], [0,0,1,0], [0,0,0,1]]

    # --- 2. Build Segment Tree on Transition Matrices ---
    # We only need to combine transitions, so segtree is on T_1...T_{N'-1}
    seg_tree = [identity_matrix] * (2 * N_prime)
    for i in range(1, N_prime):
        seg_tree[N_prime + i] = trans_matrices[i]
    
    for i in range(N_prime - 1, 0, -1):
        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
        
        # Get the start matrix for the first element
        res_matrix = start_matrices[l_idx]
        
        # Query segment tree for product of transition matrices [l_idx+1, r_idx]
        if l_idx < r_idx:
            l, r = (l_idx + 1) + N_prime, (r_idx) + N_prime + 1
            trans_prod = identity_matrix
            while l < r:
                if l & 1:
                    trans_prod = mat_mul(trans_prod, seg_tree[l])
                    l += 1
                if r & 1:
                    r -= 1
                    trans_prod = mat_mul(trans_prod, seg_tree[r])
                l >>= 1
                r >>= 1
            res_matrix = mat_mul(res_matrix, trans_prod)
            
        # The answer is the final TOTAL_T, which is the (3,2) element 
        # of the product matrix starting from the [0,0,0,1] state.
        print(res_matrix[3][2])

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