結果

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

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, Q, P = map(int, input[ptr:ptr+3])
    ptr += 3
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N

    # Precompute prefix zeros
    prefix_zeros = [0] * (N + 1)
    for i in range(N):
        prefix_zeros[i+1] = prefix_zeros[i] + (A[i] == 0)

    # Precompute multiply_mod for all possible a and r
    multiply_mod = [[0] * P for _ in range(P)]
    for a in range(P):
        for r in range(P):
            multiply_mod[a][r] = (r * a) % P

    # Process each query
    output = []
    for _ in range(Q):
        L = int(input[ptr])
        R = int(input[ptr+1])
        K = int(input[ptr+2])
        ptr += 3

        if K == 0:
            if prefix_zeros[R] - prefix_zeros[L-1] > 0:
                output.append("Yes")
            else:
                output.append("No")
        else:
            # Extract non-zero elements in the interval
            elements = []
            for i in range(L-1, R):
                val = A[i]
                if val != 0:
                    elements.append(val)
            if not elements:
                output.append("No")
                continue

            mask = 0
            for a in elements:
                multiplied = 0
                # Iterate through all possible remainders in the current mask
                # This loop can be optimized using bit manipulation tricks in PyPy
                for r in range(P):
                    if (mask >> r) & 1:
                        new_r = multiply_mod[a][r]
                        multiplied |= (1 << new_r)
                new_mask = mask | multiplied | (1 << a)
                mask = new_mask

            if (mask >> K) & 1:
                output.append("Yes")
            else:
                output.append("No")

    print('\n'.join(output))

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