結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    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 % MOD)
        b.append(bi % MOD)

    class SegmentTree:
        def __init__(self, a, b):
            self.n = len(a)
            self.size = 1
            while self.size < self.n:
                self.size <<=1
            self.tree_a = [1] * (2 * self.size)
            self.tree_b = [0] * (2 * self.size)
            for i in range(self.n):
                self.tree_a[self.size + i] = a[i]
                self.tree_b[self.size + i] = b[i]
            for i in range(self.size -1, 0, -1):
                self.tree_a[i] = (self.tree_a[2*i] * self.tree_a[2*i+1]) % MOD
                self.tree_b[i] = (self.tree_b[2*i] * self.tree_a[2*i+1] + self.tree_b[2*i+1]) % MOD

        def query_a_b(self, l, r):
            res_a = 1
            res_b = 0
            l += self.size
            r += self.size
            while l < r:
                if l % 2 ==1:
                    res_a = (res_a * self.tree_a[l]) % MOD
                    res_b = (res_b * self.tree_a[l] + self.tree_b[l]) % MOD
                    l +=1
                if r % 2 ==1:
                    r -=1
                    res_a = (res_a * self.tree_a[r]) % MOD
                    res_b = (res_b * self.tree_a[r] + self.tree_b[r]) % 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

        if l >= r:
            results.append(x % MOD)
            continue

        m = 0
        current_x = x % MOD
        for k in range(l, r):
            idx = k ^ p
            current_x = (a[idx] * current_x + b[idx]) % MOD

        results.append(current_x % MOD)

    for res in results:
        print(res)

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