結果

問題 No.1891 Static Xor Range Composite Query
ユーザー gew1fw
提出日時 2025-06-12 15:15:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,899 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 77,176 KB
最終ジャッジ日時 2025-06-12 15:15:16
合計ジャッジ時間 9,673 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 998244353

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, Q = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    a = []
    b = []
    for _ in range(N):
        ai = int(input[ptr])
        bi = int(input[ptr+1])
        a.append(ai)
        b.append(bi)
        ptr += 2
    
    size = 1
    while size < N:
        size <<= 1
    tree_A = [1] * (2 * size)
    tree_B = [0] * (2 * size)
    
    for i in range(N):
        tree_A[size + i] = a[i] % MOD
        tree_B[size + i] = b[i] % MOD
    
    for i in range(size - 1, 0, -1):
        tree_A[i] = (tree_A[i << 1] * tree_A[i << 1 | 1]) % MOD
        tree_B[i] = (tree_B[i << 1] * tree_A[i << 1 | 1] + tree_B[i << 1 | 1]) % MOD
    
    def query(l, r):
        res_A = 1
        res_B = 0
        l += size
        r += size
        while l < r:
            if l % 2:
                res_A = (res_A * tree_A[l]) % MOD
                res_B = (res_B * tree_A[l] + tree_B[l]) % MOD
                l += 1
            if r % 2:
                r -= 1
                res_A = (res_A * tree_A[r]) % MOD
                res_B = (res_B * tree_A[r] + tree_B[r]) % MOD
            l >>= 1
            r >>= 1
        return (res_A, res_B)
    
    output = []
    for _ in range(Q):
        l = int(input[ptr])
        r = int(input[ptr+1])
        p = int(input[ptr+2])
        x = int(input[ptr+3])
        ptr += 4
        
        functions = []
        for k in range(r - l):
            idx = (l + k) ^ p
            functions.append((a[idx] % MOD, b[idx] % MOD))
        
        A_total = 1
        B_total = 0
        for a_i, b_i in functions:
            A_total = (A_total * a_i) % MOD
            B_total = (B_total * a_i + b_i) % MOD
        
        res = (A_total * x + B_total) % MOD
        output.append(res)
    
    print('\n'.join(map(str, output)))

if __name__ == '__main__':
    main()
0