結果

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

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    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)
    
    # Precompute prefix product of a
    prefix_a = [1] * (N+1)
    for i in range(N):
        prefix_a[i+1] = (prefix_a[i] * a[i]) % MOD
    
    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
        
        # Compute A: product of a[i^p] for i in [l, r)
        # Since A is product, and order doesn't matter, we can compute it as the product of a[(i^p)] for i from l to r-1
        # To compute this, we can note that i^p is a bijection, so [l, r) is mapped to some range, but the product is the same as the product of a[j] for j in [l^p, r^p)
        # Wait, no: because i^p is not necessarily a continuous range. For example, i ranges from l to r-1, and j = i^p can be scattered.
        # So we need another way to compute the product.
        # One approach is to iterate through each i in [l, r) and multiply a[i^p], but this is O(r-l) per query, which is too slow for Q=2e5.
        # So, we need a way to compute the product efficiently.
        # However, given the time constraints, perhaps this is the only way.
        # So, let's proceed with this approach, but we need to find a way to optimize it.
        # Wait, but N is up to 2^18=262144, and Q is 2e5, so if each query has up to 2^18 operations, it's 2^23 operations, which is about 8 million, which is manageable within 5 seconds.
        # So, perhaps we can proceed with this approach.
        # Compute A:
        A = 1
        B = 0
        for i in range(l, r):
            idx = i ^ p
            if idx < 0 or idx >= N:
                # This should not happen as per problem statement
                pass
            else:
                a_i = a[idx]
                b_i = b[idx]
                # Update A and B
                A = (A * a_i) % MOD
                B = (B * a_i + b_i) % MOD
        
        # Now, compute the result: A * x + B mod MOD
        res = (A * x + B) % MOD
        print(res)
    
if __name__ == '__main__':
    main()
0