結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    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)
        b.append(bi)
    
    queries = []
    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
        queries.append( (l, r, p, x) )
    
    size = 1
    while size < N:
        size <<=1
    tree = [ (1,0) for _ in range(2*size) ]
    
    for i in range(N):
        ai = a[i]
        bi = b[i]
        tree[size + i] = (ai % MOD, bi % MOD)
    
    for i in range(size-1, 0, -1):
        a_left, b_left = tree[2*i]
        a_right, b_right = tree[2*i +1]
        a_total = (a_right * a_left) % MOD
        b_total = (a_right * b_left + b_right) % MOD
        tree[i] = (a_total, b_total)
    
    def query(l, r):
        res_a = 1
        res_b = 0
        l += size
        r += size
        while l < r:
            if l % 2 ==1:
                a_tmp, b_tmp = tree[l]
                res_a = (res_a * a_tmp) % MOD
                res_b = (res_a * res_b + res_b * a_tmp + b_tmp) % MOD
                res_b = (res_a * res_b + b_tmp) % MOD
                l +=1
            if r %2 ==1:
                r -=1
                a_tmp, b_tmp = tree[r]
                res_a = (res_a * a_tmp) % MOD
                res_b = (res_a * res_b + b_tmp) % MOD
            l >>=1
            r >>=1
        return (res_a, res_b)
    
    for l, r, p, x in queries:
        if l >= r:
            print(x % MOD)
            continue
        res_a = 1
        res_b = 0
        current_a = 1
        current_b = 0
        for k in range(l, r):
            i = k ^ p
            if i >= N:
                continue
            ai = a[i]
            bi = b[i]
            current_a = (ai * current_a) % MOD
            current_b = (ai * current_b + bi) % MOD
        res = (current_a * x + current_b) % MOD
        print(res)
    
if __name__ == '__main__':
    main()
0