結果

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

ソースコード

diff # 

import bisect

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    Q = int(data[idx+1])
    idx +=2
    A = list(map(int, data[idx:idx+N]))
    idx +=N
    queries = []
    for _ in range(Q):
        l = int(data[idx])
        r = int(data[idx+1])
        p = int(data[idx+2])
        queries.append((l, r, p))
        idx +=3
    
    # Sort the array
    sorted_A = sorted(A)
    
    # Precompute prefix_prod and suffix_prod_minus_1
    prefix_prod = [1] * (N + 1)
    for i in range(N):
        prefix_prod[i+1] = prefix_prod[i] * sorted_A[i] % MOD
    
    suffix_prod_minus_1 = [1] * (N + 1)
    for i in range(N-1, -1, -1):
        temp = sorted_A[i] - 1
        if temp < 0:
            temp = 0
        suffix_prod_minus_1[i] = suffix_prod_minus_1[i+1] * temp % MOD
    
    # Precompute x_i for each element in sorted_A
    x = []
    for a in sorted_A:
        temp = a - 1
        if temp <= 0:
            xi = 0
        else:
            temp_mod = temp % MOD
            if temp_mod == 0:
                xi = 0
            else:
                xi = pow(temp_mod, MOD-2, MOD)
        x.append(xi)
    
    # Precompute DP for elementary symmetric sums
    max_p = N
    dp = [[0] * (max_p + 1) for _ in range(N + 2)]  # dp[i][p] for i in 0..N, p in 0..max_p
    dp[N][0] = 1
    for i in range(N-1, -1, -1):
        dp[i][0] = 1
        xi = x[i]
        for p in range(1, max_p + 1):
            dp[i][p] = (dp[i+1][p] + xi * dp[i+1][p-1]) % MOD
    
    # Process each query
    results = []
    for l, r, p in queries:
        res = 0
        for c in range(l, r+1):
            # Find the first index i where sorted_A[i] >= c
            i = bisect.bisect_left(sorted_A, c)
            m = N - i
            if m < p:
                cont = 0
            else:
                # Compute product_not_S
                product_not_S = prefix_prod[i]
                # Compute product_S
                product_S = suffix_prod_minus_1[i]
                # Get e_p
                if p > max_p:
                    e_p_val = 0
                else:
                    e_p_val = dp[i][p]
                # Compute contribution
                cont = product_not_S * product_S % MOD
                cont = cont * e_p_val % MOD
            res ^= cont
        results.append(res % MOD)
    
    print('\n'.join(map(str, results)))

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