#1056610 (PyPy3) No.1731 Product of Subsequence

• 問題: No.1731 Product of Subsequence
• ユーザー: lam6er
• 提出日時: 2025-03-20 21:12:21
• 言語: PyPy3 (7.3.15)
• 結果: TLE
• 実行時間: -
• コード長: 2,343 bytes
• コンパイル時間: 517 ms
• コンパイル使用メモリ: 82,608 KB
• 実行使用メモリ: 100,668 KB
• 最終ジャッジ日時: 2025-03-20 21:14:34
• 合計ジャッジ時間: 21,704 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 29 TLE * 2

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX