結果

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

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    Q = int(data[idx])
    idx +=1

    a = []
    b = []
    for _ in range(N):
        ai = int(data[idx])
        idx +=1
        bi = int(data[idx])
        idx +=1
        a.append(ai % MOD)
        b.append(bi % MOD)

    max_level = 0
    while (1 << max_level) <= N:
        max_level +=1
    max_level -=1

    logn = max_level
    blocks = [ [ [0,0] for _ in range(N) ] for __ in range(logn+1) ]

    for i in range(N):
        blocks[0][i] = (a[i], b[i])

    for level in range(1, logn+1):
        d = 1 << level
        for s in range(0, N, d):
            left_s = s
            left_d = d // 2
            right_s = s + left_d
            right_d = d // 2

            a_left, b_left = blocks[level-1][left_s]
            a_right, b_right = blocks[level-1][right_s]

            a_total = (a_left * a_right) % MOD
            b_total = (b_left * a_right % MOD + b_right) % MOD

            blocks[level][s] = (a_total, b_total)

    def get_block(level, s):
        if s + (1 << level) > N:
            return (1, 0)
        a_total, b_total = blocks[level][s]
        return (a_total, b_total)

    for _ in range(Q):
        l = int(data[idx])
        idx +=1
        r = int(data[idx])
        idx +=1
        p = int(data[idx])
        idx +=1
        x = int(data[idx])
        idx +=1

        if l >= r:
            print(x % MOD)
            continue

        A_total = 1
        B_total = 0

        for i in range(l, r):
            k = i ^ p
            if k <0 or k >= N:
                A = 1
                B = 0
            else:
                A = a[k]
                B = b[k]
            A_total = (A_total * A) % MOD
            B_total = (B_total * A + B) % MOD

        res = (A_total * x + B_total) % MOD
        print(res)

main()
0