結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1
    
    a = []
    b = []
    for _ in range(N):
        ai = int(data[ptr])
        ptr += 1
        bi = int(data[ptr])
        ptr += 1
        a.append(ai)
        b.append(bi)
    
    size = 1
    while size < N:
        size <<= 1
    
    class SegmentTree:
        def __init__(self, a, b):
            self.n = len(a)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.tree = [ (1,0) for _ in range(2*self.size) ]
            for i in range(self.n):
                ai = a[i]
                bi = b[i]
                self.tree[self.size + i] = (ai, bi)
            for i in range(self.size-1, 0, -1):
                left = self.tree[2*i]
                right = self.tree[2*i+1]
                a_total = (left[0] * right[0]) % MOD
                b_total = (left[1] * right[0] + right[1]) % MOD
                self.tree[i] = (a_total, b_total)
        
        def query(self, l, r):
            res_a = 1
            res_b = 0
            l += self.size
            r += self.size
            while l < r:
                if l % 2 == 1:
                    a, b = self.tree[l]
                    res_a = (res_a * a) % MOD
                    res_b = (res_b * a + b) % MOD
                    l += 1
                if r % 2 == 1:
                    r -= 1
                    a, b = self.tree[r]
                    res_a = (res_a * a) % MOD
                    res_b = (res_b * a + b) % MOD
                l >>= 1
                r >>= 1
            return (res_a, res_b)
    
    st = SegmentTree(a, b)
    
    results = []
    for _ in range(Q):
        l = int(data[ptr])
        ptr += 1
        r = int(data[ptr])
        ptr += 1
        p = int(data[ptr])
        ptr += 1
        x = int(data[ptr])
        ptr += 1
        
        current_l = l
        current_r = r
        current_p = p
        
        functions = []
        for k in range(current_r - current_l):
            idx = (current_l + k) ^ current_p
            if idx >= N:
                idx = idx % N
            functions.append( (a[idx], b[idx]) )
        
        a_total = 1
        b_total = 0
        for ai, bi in functions:
            a_total = (a_total * ai) % MOD
            b_total = (b_total * ai + bi) % MOD
        
        res = (a_total * x + b_total) % MOD
        results.append(res)
    
    print('\n'.join(map(str, results)))

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