結果

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

ソースコード

diff # 

import sys

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

    # Precompute prefix counts for each residue
    prefix = [[0]*(N+1) for _ in range(P)]
    for x in range(P):
        cnt = 0
        prefix[x][0] = 0
        for i in range(1, N+1):
            if A[i-1] == x:
                cnt += 1
            prefix[x][i] = cnt

    # Precompute transformation table: pre_transform[a][x] = (x * a) % P
    pre_transform = [[(x * a) % P for x in range(P)] for a in range(P)]

    # Precompute mask and zero_mask for each L and R
    mask = [[0]*(N+2) for _ in range(N+2)]  # Using N+2 to avoid index issues
    zero_mask = [[False]*(N+2) for _ in range(N+2)]

    for L in range(1, N+1):
        current_mask = 0
        current_zero = False
        for R in range(L, N+1):
            a = A[R-1]
            if a == 0:
                current_zero = True
            else:
                multiplied_bits = 0
                x = current_mask
                while x:
                    lsb = x & -x
                    pos = (lsb.bit_length() - 1)
                    y = pre_transform[a][pos]
                    multiplied_bits |= (1 << y)
                    x ^= lsb
                new_mask = current_mask | multiplied_bits | (1 << a)
                current_mask = new_mask
            mask[L][R] = current_mask
            zero_mask[L][R] = current_zero

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

        if K == 0:
            if zero_mask[L][R]:
                output.append("Yes")
            else:
                output.append("No")
        else:
            if prefix[K][R] - prefix[K][L-1] > 0:
                output.append("Yes")
            else:
                if (mask[L][R] & (1 << K)) != 0:
                    output.append("Yes")
                else:
                    output.append("No")

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

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