結果

問題 No.1349 Subset Product Queries
ユーザー lam6er
提出日時 2025-04-15 22:27:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,066 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 314,728 KB
最終ジャッジ日時 2025-04-15 22:30:15
合計ジャッジ時間 5,033 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    Q = int(data[idx+1])
    P = int(data[idx+2])
    idx +=3
    A = list(map(int, data[idx:idx+N]))
    idx +=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 non_zero_positions and their values mod P
    non_zero_positions = []
    non_zero_values = []
    for i in range(N):
        if A[i] !=0:
            non_zero_positions.append(i+1)  # 1-based index
            non_zero_values.append(A[i] % P)
    
    # Precompute multiplication table
    mul_table = [[0]*P for _ in range(P)]
    for j in range(P):
        for a in range(P):
            mul_table[j][a] = (j * a) % P
    
    # Process queries
    for _ in range(Q):
        L = int(data[idx])
        R = int(data[idx+1])
        K = int(data[idx+2])
        idx +=3
        
        if K ==0:
            if prefix_zeros[R] - prefix_zeros[L-1] >0:
                print("Yes")
            else:
                print("No")
        else:
            # Find non-zero elements in [L, R]
            left = bisect.bisect_left(non_zero_positions, L)
            right = bisect.bisect_right(non_zero_positions, R)
            elements = non_zero_values[left:right]
            if not elements:
                print("No")
                continue
            
            # Compute DP
            mask = 0
            for a in elements:
                multiplied_mask = 0
                j = mask
                while j:
                    lsb = j & -j
                    bit = (lsb).bit_length() -1
                    multiplied_mask |= (1 << mul_table[bit][a])
                    j ^= lsb
                new_mask = mask | multiplied_mask | (1 << a)
                mask = new_mask
            
            if (mask & (1 << K)) !=0:
                print("Yes")
            else:
                print("No")

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