結果

問題 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)
ユーザー gew1fw
提出日時 2025-06-12 19:20:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 693 ms / 2,000 ms
コード長 1,567 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 361,252 KB
最終ジャッジ日時 2025-06-12 19:20:53
合計ジャッジ時間 6,868 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, Q = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    queries = []
    max_A = max(A)
    for _ in range(Q):
        l = int(input[ptr])
        r = int(input[ptr+1])
        p = int(input[ptr+2])
        queries.append((l, r, p))
        ptr +=3
    
    # Sort the array
    B = sorted(A)
    n = N
    
    # Precompute prefix products
    prefix = [1] * (n + 1)
    for i in range(n):
        prefix[i+1] = (prefix[i] * B[i]) % MOD
    
    # Precompute dp[i][p]
    max_p = N
    dp = [[0] * (max_p + 1) for _ in range(n + 2)]  # dp[i][p], i is 0-based up to n
    dp[n][0] = 1
    for i in range(n-1, -1, -1):
        current = B[i]
        for p in range(0, (n - i) + 1):
            if p == 0:
                dp[i][p] = ( (current - 1) * dp[i+1][p] ) % MOD
            else:
                term1 = ( (current - 1) * dp[i+1][p] ) % MOD
                term2 = dp[i+1][p-1]
                dp[i][p] = (term1 + term2) % MOD
    
    # Process each query
    for l, r, p in queries:
        res = 0
        for c in range(l, r+1):
            # Find the first index >=c in B
            k = bisect.bisect_left(B, c)
            product_Y = prefix[k]
            m = n - k
            if p > m or p < 0:
                total = 0
            else:
                total = (product_Y * dp[k][p]) % MOD
            res ^= total
        print(res % MOD)
    
if __name__ == "__main__":
    main()
0