結果

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

ソースコード

diff # 

import sys
import math

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_list = []
    b_list = []
    for _ in range(N):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        a_list.append(a)
        b_list.append(b)
    
    B = int(math.sqrt(N)) + 1
    pre = [ [ (1, 0) for _ in range(B) ] for _ in range(N // B + 1) ]
    suf = [ [ (1, 0) for _ in range(B) ] for _ in range(N // B + 1) ]
    
    for i in range(N):
        block = i // B
        pos = i % B
        if pos == 0:
            pre[block][pos] = (a_list[i], b_list[i])
            suf[block][pos] = (a_list[i], b_list[i])
        else:
            a_pre, b_pre = pre[block][pos-1]
            a_pre_new = (a_pre * a_list[i]) % MOD
            b_pre_new = (b_pre * a_list[i] + b_list[i]) % MOD
            pre[block][pos] = (a_pre_new, b_pre_new)
            
            a_suf, b_suf = suf[block][pos]
            a_suf_new = (a_list[i] * a_suf) % MOD
            b_suf_new = (b_list[i] * a_suf + b_suf) % MOD
            suf[block][pos] = (a_suf_new, b_suf_new)
    
    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
        
        m = r - l
        a = 1
        b = 0
        
        for i in range(l, r):
            k = i ^ p
            ai = a_list[k]
            bi = b_list[k]
            a = (a * ai) % MOD
            b = (b * ai + bi) % MOD
        
        res = (a * x + b) % MOD
        print(res)

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