結果

問題 No.1731 Product of Subsequence
ユーザー lam6er
提出日時 2025-03-20 20:51:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,087 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 163,792 KB
最終ジャッジ日時 2025-03-20 20:51:55
合計ジャッジ時間 6,780 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 10**9 + 7

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

def main():
    n, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    if K == 1:
        print((pow(2, n, MOD) - 1) % MOD)
        return
    
    factors = list(prime_factors(K))
    primes = [p for p, _ in factors]
    exponents = [e for _, e in factors]
    m = len(primes)
    
    total = [0] * m
    ts = []
    for a in A:
        t = []
        for i in range(m):
            p = primes[i]
            e = 0
            while a % p == 0:
                e += 1
                a = a // p
            t.append(e)
            total[i] += e
        ts.append(t)
    
    for i in range(m):
        if total[i] < exponents[i]:
            print(0)
            return
    
    pow2 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow2[i] = (pow2[i - 1] * 2) % MOD
    
    dp = defaultdict(int)
    initial_state = tuple(sorted((i, 0) for i in range(m)))
    dp[initial_state] = 1
    
    ans = 0
    
    for j in range(n):
        current_t = ts[j]
        tmp_dp = defaultdict(int)
        for s in list(dp.keys()):
            cnt = dp[s]
            tmp_dp[s] = (tmp_dp[s] + cnt) % MOD
            
            new_unfinished = []
            for (i, c) in s:
                new_c = c + current_t[i]
                if new_c < exponents[i]:
                    new_unfinished.append((i, new_c))
            
            new_unfinished_sorted = tuple(sorted(new_unfinished))
            if not new_unfinished:
                remaining = n - j - 1
                ans = (ans + cnt * pow2[remaining]) % MOD
            else:
                tmp_dp[new_unfinished_sorted] = (tmp_dp[new_unfinished_sorted] + cnt) % MOD
        
        dp = tmp_dp
    
    print(ans % MOD)

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