結果

問題 No.2369 Some Products
ユーザー lam6er
提出日時 2025-04-16 15:49:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,367 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 81,944 KB
実行使用メモリ 84,752 KB
最終ジャッジ日時 2025-04-16 15:51:01
合計ジャッジ時間 4,254 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    P = list(map(int, data[ptr:ptr+N]))
    ptr += N
    
    # Preprocess P to mod 998244353
    for i in range(N):
        P[i] %= mod
        if P[i] < 0:
            P[i] += mod
    
    # Precompute prefix sums for K=1 queries
    sum_prefix = [0] * (N + 1)
    for i in range(N):
        sum_prefix[i+1] = (sum_prefix[i] + P[i]) % mod
    
    Q = int(data[ptr])
    ptr += 1
    results = []
    for _ in range(Q):
        A = int(data[ptr])
        B = int(data[ptr+1])
        K = int(data[ptr+2])
        ptr += 3
        
        L = B - A + 1
        if K > L:
            results.append(0)
            continue
        
        if K == 1:
            res = (sum_prefix[B] - sum_prefix[A-1]) % mod
            results.append(res)
            continue
        
        # Initialize DP array
        max_k = K
        dp = [0] * (max_k + 1)
        dp[0] = 1
        
        for idx in range(A-1, B):
            p = P[idx]
            current_max_k = min(max_k, idx - (A-1) + 1)
            for k in range(current_max_k, 0, -1):
                dp[k] = (dp[k] + dp[k-1] * p) % mod
        
        results.append(dp[K] % mod)
    
    print('\n'.join(map(str, results)))

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