結果

問題 No.1349 Subset Product Queries
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:23:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,312 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 75,864 KB
最終ジャッジ日時 2025-06-12 18:23:27
合計ジャッジ時間 4,799 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(lambda x: int(x) % P, input[ptr:ptr+N]))
    ptr += N

    # Precompute the possible remainders for each interval [i, j]
    pre = [[0] * (N + 1) for _ in range(N + 1)]  # pre[i][j] is the bitmask for interval [i, j]

    for i in range(N):
        current_mask = 0
        a = A[i]
        current_mask |= 1 << a
        pre[i+1][i+1] = current_mask
        for j in range(i + 1, N):
            a_j = A[j]
            temp_mask = 0
            mask = pre[i+1][j]  # previous mask up to j (exclusive)
            # Multiply each existing remainder by a_j and add a_j itself
            while mask:
                lsb = mask & -mask
                r = (lsb.bit_length() - 1)
                product = (r * a_j) % P
                temp_mask |= 1 << product
                mask ^= lsb
            # Add the current a_j itself (as a new subset)
            temp_mask |= 1 << a_j
            # Combine with previous subsets (which do not include a_j)
            new_mask = pre[i+1][j] | temp_mask
            pre[i+1][j+1] = new_mask

    # Precompute the prefix sum of zeros to quickly check for K=0
    zero_prefix = [0] * (N + 1)
    for i in range(N):
        zero_prefix[i+1] = zero_prefix[i] + (A[i] == 0)

    # Process each query
    output = []
    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:
            # Check if there's at least one zero in the interval
            zeros = zero_prefix[R] - zero_prefix[L-1]
            output.append("Yes" if zeros > 0 else "No")
        else:
            # Check if there are non-zero elements
            total = R - L + 1
            zeros = zero_prefix[R] - zero_prefix[L-1]
            if zeros == total:
                output.append("No")
                continue
            # Check the precomputed mask
            mask = pre[L][R]
            if (mask >> K) & 1:
                output.append("Yes")
            else:
                output.append("No")

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

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