結果

問題 No.1349 Subset Product Queries
ユーザー gew1fw
提出日時 2025-06-12 18:22:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,873 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 325,468 KB
最終ジャッジ日時 2025-06-12 18:22:26
合計ジャッジ時間 4,816 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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_zeros
    prefix_zeros = [0] * (N + 1)
    for i in range(N):
        prefix_zeros[i+1] = prefix_zeros[i] + (1 if A[i] == 0 else 0)

    # Precompute trans[a][x] = (x * a) % P for all a and x
    trans = []
    for a in range(P):
        t = []
        for x in range(P):
            t.append((x * a) % P)
        trans.append(t)

    # Process each query
    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_zeros[R] - prefix_zeros[L-1]
            print("Yes" if zeros > 0 else "No")
        else:
            # Check non-zero elements in [L, R]
            mask = 0
            found = False
            for i in range(L-1, R):
                a = A[i]
                if a == 0:
                    continue
                a_mod = a % P
                if a_mod == 0:
                    continue  # since K is non-zero, but a_mod is zero, but this is already handled.

                product_mask = 0
                temp_mask = mask
                x = 0
                while temp_mask != 0 and x < P:
                    if temp_mask & 1:
                        product_mask |= 1 << trans[a_mod][x]
                    temp_mask >>= 1
                    x += 1

                new_mask = mask | product_mask | (1 << a_mod)
                if (new_mask & (1 << K)) != 0:
                    found = True
                    break
                mask = new_mask

            print("Yes" if found else "No")

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