結果

問題 No.1349 Subset Product Queries
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:19:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,614 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 311,908 KB
最終ジャッジ日時 2025-03-20 21:20:34
合計ジャッジ時間 5,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from math import isqrt

def input():
    return stdin.read()

def factorize(n):
    factors = {}
    i = 2
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 1
    if n > 1:
        factors[n] = 1
    return factors

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

    queries = []
    for _ in range(Q):
        L = int(data[ptr])-1  # 0-based
        R = int(data[ptr+1])-1
        K = int(data[ptr+2])
        queries.append( (L, R, K) )
        ptr +=3

    # Preprocessing for K=0 case
    # 1. Check for A[j] mod P ==0
    has_zero = [0]*(N+1)
    for i in range(N):
        has_zero[i+1] = has_zero[i] + (1 if A[i] % P ==0 else 0)
    
    # Factorize P
    factors = factorize(P)
    if not factors:
        # P is 1
        pass
    else:
        primes = list(factors.items())
    
    # Precompute prefix sums for exponents
    ex_prefix = {}
    for p, e in primes:
        ex = [0]*(N+1)
        for i in range(N):
            a = A[i]
            cnt =0
            while a % p ==0 and a !=0:
                cnt +=1
                a = a //p
            ex[i+1] = ex[i] + cnt
        ex_prefix[p] = ex
    
    # Preprocessing for K!=0 case: DP for each L
    # Since P can be up to 5000, N is 5000, and Q is 2e5, precompute masks for each L and R.
    MOD = P
    pre = [ [0]*(N) for _ in range(N) ]  # pre[L][R] = mask for [L, R]

    for L in range(N):
        current_mask = 0
        for R in range(L, N):
            a = A[R] % MOD
            if a == 0:
                new_part = 0
            else:
                new_part = 0
                if current_mask ==0:
                    new_part = 0
                else:
                    tmp = current_mask
                    while tmp:
                        lsb = tmp & -tmp
                        idx = (lsb).bit_length() -1
                        m = (idx * a) % MOD
                        new_part |= 1 << m
                        tmp ^= lsb
            current_mask = (current_mask | new_part)
            if a !=0:
                current_mask |= 1 << a
            current_mask &= (1 << MOD) -1
            pre[L][R] = current_mask

    # Process queries
    results = []
    for L, R, K in queries:
        if K ==0:
            # Check if any zero in [L, R]
            count = has_zero[R+1] - has_zero[L]
            if count >0:
                results.append("Yes")
                continue
            if P ==1:
                # Any non-empty subset, mod 1 is 0
                results.append("Yes")
                continue
            # Check if all primes have enough exponents
            ok = True
            for p, e in primes:
                total = ex_prefix[p][R+1] - ex_prefix[p][L]
                if total < e:
                    ok = False
                    break
            if ok:
                results.append("Yes")
            else:
                results.append("No")
        else:
            if P ==1:
                # K must be 0, but K!=0 here
                results.append("No")
                continue
            if L > R:
                results.append("No")
                continue
            mask = pre[L][R]
            if (mask & (1 << K)) !=0:
                results.append("Yes")
            else:
                results.append("No")
    
    print('\n'.join(results))

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