結果

問題 No.1349 Subset Product Queries
ユーザー gew1fw
提出日時 2025-06-12 18:22:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,517 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 171,088 KB
最終ジャッジ日時 2025-06-12 18:23:03
合計ジャッジ時間 4,799 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    Q = int(input[ptr]); ptr +=1
    P = int(input[ptr]); ptr +=1
    
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    
    # Precompute prefix sum of zeros
    prefix_zero = [0] * (N + 1)
    for i in range(1, N+1):
        prefix_zero[i] = prefix_zero[i-1] + (1 if A[i-1] == 0 else 0)
    
    for _ in range(Q):
        L = int(input[ptr]); ptr +=1
        R = int(input[ptr]); ptr +=1
        K = int(input[ptr]); ptr +=1
        
        if K == 0:
            zeros = prefix_zero[R] - prefix_zero[L-1]
            print("Yes" if zeros > 0 else "No")
            continue
        
        # Collect non-zero elements in [L, R]
        non_zero = []
        for i in range(L-1, R):
            a = A[i]
            if a != 0:
                non_zero.append(a % P)
        
        if not non_zero:
            print("No")
            continue
        
        possible = set()
        found = False
        for a in non_zero:
            a_mod = a % P
            new_possible = {a_mod}
            for s in possible:
                new_s = (s * a_mod) % P
                new_possible.add(new_s)
            # Update possible
            for s in new_possible:
                if s not in possible:
                    possible.add(s)
            if K in possible:
                found = True
                break
        print("Yes" if found else "No")

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