結果

問題 No.2313 Product of Subsequence (hard)
ユーザー lam6er
提出日時 2025-04-16 16:28:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,784 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 268,808 KB
最終ジャッジ日時 2025-04-16 16:29:51
合計ジャッジ時間 14,256 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 998244353

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 factors

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 = factorize(k)
    primes = list(factors.keys())
    m = len(primes)
    if m == 0:
        print((pow(2, n, MOD) - 1) % MOD)
        return
    
    G = []
    C = []
    for x in a:
        ex = {}
        has = False
        for p in primes:
            e = 0
            tmp = x
            while tmp % p == 0 and tmp != 0:
                e += 1
                tmp = tmp // p
            ex[p] = e
            if e > 0:
                has = True
        if has:
            G.append(ex)
        else:
            C.append(x)
    
    lenG = len(G)
    total_G_subsets = (pow(2, lenG, MOD) - 1) % MOD
    forbidden = 0
    
    for mask in range(1, 1 << m):
        bits = bin(mask).count('1')
        T = [primes[i] for i in range(m) if (mask & (1 << i))]
        required = [factors[p] for p in T]
        G_T = []
        for ex in G:
            valid = True
            for i, p in enumerate(T):
                if ex[p] >= required[i]:
                    valid = False
                    break
            if valid:
                G_T.append(ex)
        
        exponents_list = []
        for ex in G_T:
            el = [ex[p] for p in T]
            exponents_list.append(el)
        
        dp = defaultdict(int)
        initial_state = tuple([0] * len(T))
        dp[initial_state] = 1
        
        for el in exponents_list:
            new_dp = defaultdict(int)
            for state in dp:
                new_dp[state] = (new_dp[state] + dp[state]) % MOD
                new_state = list(state)
                valid = True
                for i in range(len(new_state)):
                    new_state[i] += el[i]
                    if new_state[i] >= required[i]:
                        valid = False
                        break
                if valid:
                    new_state = tuple(new_state)
                    new_dp[new_state] = (new_dp[new_state] + dp[state]) % MOD
            dp = new_dp
        
        count = (sum(dp.values()) - 1) % MOD
        sign = (-1) ** (bits + 1)
        forbidden = (forbidden + sign * count) % MOD
    
    valid_G_subsets = (total_G_subsets - forbidden) % MOD
    powC = pow(2, len(C), MOD)
    answer = (valid_G_subsets * powC) % MOD
    print(answer)

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