結果

問題 No.1731 Product of Subsequence
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:57:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,343 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 100,656 KB
最終ジャッジ日時 2025-03-20 18:59:32
合計ジャッジ時間 22,838 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

MOD = 10**9 + 7

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

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    
    if K == 1:
        print((pow(2, N, MOD) - 1) % MOD)
        return
    
    factors = factorize(K)
    m = len(factors)
    primes = [p for p, e in factors]
    required = [e for p, e in factors]
    
    # Check if each prime is present in at least one element
    has_prime = [False] * m
    for a in A:
        for i in range(m):
            p = primes[i]
            temp = a
            cnt = 0
            while temp % p == 0 and temp != 0:
                cnt += 1
                temp = temp // p
            if cnt > 0:
                has_prime[i] = True
    
    if not all(has_prime):
        print(0)
        return
    
    # Precompute exponents for each element
    exponents_list = []
    for a in A:
        exps = []
        for (p, e) in factors:
            temp = a
            cnt = 0
            while temp % p == 0 and temp != 0:
                cnt += 1
                temp = temp // p
            exps.append(cnt)
        exponents_list.append(exps)
    
    # Dynamic programming
    dp = defaultdict(int)
    initial_state = tuple([0]*m)
    dp[initial_state] = 1
    
    for exps in exponents_list:
        new_dp = defaultdict(int, dp)
        for state in list(dp.keys()):
            current_count = dp[state]
            new_state = list(state)
            for i in range(m):
                new_state[i] = min(state[i] + exps[i], required[i])
            new_state_tuple = tuple(new_state)
            new_dp[new_state_tuple] = (new_dp[new_state_tuple] + current_count) % MOD
        dp = new_dp
    
    result = 0
    for state in dp:
        valid = True
        for i in range(m):
            if state[i] < required[i]:
                valid = False
                break
        if valid:
            result = (result + dp[state]) % MOD
    print(result % MOD)

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