結果

問題 No.1349 Subset Product Queries
ユーザー lam6er
提出日時 2025-04-15 22:22:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,007 bytes
コンパイル時間 465 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 311,188 KB
最終ジャッジ日時 2025-04-15 22:25:08
合計ジャッジ時間 5,097 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 7 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
    queries = []
    for _ in range(Q):
        L = int(input[ptr]) - 1
        R = int(input[ptr+1]) - 1
        K = int(input[ptr+2])
        queries.append((L, R, K))
        ptr += 3

    # Precompute prefix sums for zero counts
    zero_prefix = [0] * (N + 1)
    for i in range(N):
        zero_prefix[i + 1] = zero_prefix[i] + (A[i] % P == 0)

    # Precompute possible mod values for non-zero elements using bitmask DP
    dp = [[0] * N for _ in range(N)]
    for L in range(N):
        current = 0
        has_non_zero = False
        for R in range(L, N):
            a = A[R] % P
            if a != 0:
                has_non_zero = True
                new_current = 0
                if current == 0:
                    new_current = 1 << a
                else:
                    # Iterate through all set bits in current
                    mask = current
                    while mask:
                        # Extract the least significant set bit
                        i = (mask & -mask).bit_length() - 1
                        mask ^= (1 << i)
                        j = (i * a) % P
                        new_current |= (1 << j)
                    new_current |= (1 << a)
                current = new_current
                dp[L][R] = current
            else:
                dp[L][R] = current if has_non_zero else 0

    # Process each query
    output = []
    for L, R, K in queries:
        if K == 0:
            if zero_prefix[R + 1] - zero_prefix[L] > 0:
                output.append("Yes")
            else:
                output.append("No")
        else:
            mask = dp[L][R]
            if mask & (1 << K):
                output.append("Yes")
            else:
                output.append("No")
    
    print('\n'.join(output))

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