結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    A = list(map(int, data[idx:idx+N]))
    idx += N

    if K == 1:
        print((pow(2, N, MOD) - 1) % MOD)
        return

    def factorize(k):
        factors = {}
        if k == 1:
            return 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

    factors = factorize(K)
    if not factors:
        print(0)
        return

    primes = list(factors.keys())
    m = len(primes)
    exponents = [factors[p] for p in primes]

    sig_elements = []
    non_sig_count = 0

    for a in A:
        is_coprime = True
        for p in primes:
            if a % p == 0:
                is_coprime = False
                break
        if is_coprime:
            non_sig_count += 1
        else:
            sig_elements.append(a)

    S = len(sig_elements)
    if S == 0:
        print(0)
        return

    sig_exponents = []
    for a in sig_elements:
        e_list = []
        for p in primes:
            cnt = 0
            x = a
            while x % p == 0:
                cnt += 1
                x //= p
            e_list.append(cnt)
        sig_exponents.append(e_list)

    pow2T = pow(2, non_sig_count, MOD)
    total = 0

    from itertools import combinations
    from collections import defaultdict

    for mask in range(0, 1 << m):
        Q = []
        for i in range(m):
            if (mask >> i) & 1:
                Q.append(i)
        k = len(Q)
        sign = (-1) ** k

        Q_exponents = [exponents[i] for i in Q]
        Q_primes = [primes[i] for i in Q]

        compatible = []
        for i in range(S):
            valid = True
            for q in Q:
                if sig_exponents[i][q] >= exponents[q]:
                    valid = False
                    break
            if valid:
                compat_exponents = [sig_exponents[i][q] for q in Q]
                compatible.append(compat_exponents)

        if not compatible:
            F = 0
        else:
            dp = defaultdict(int)
            initial_state = tuple([0] * len(Q))
            dp[initial_state] = 1

            for exponents_list in compatible:
                new_dp = defaultdict(int)
                for state, count in dp.items():
                    new_dp[state] = (new_dp[state] + count) % MOD

                for state, count in dp.items():
                    new_state = list(state)
                    for i in range(len(Q)):
                        new_state[i] += exponents_list[i]
                    new_state_tuple = tuple(new_state)
                    valid = True
                    for i in range(len(Q)):
                        if new_state[i] >= Q_exponents[i]:
                            valid = False
                            break
                    if valid:
                        new_dp[new_state_tuple] = (new_dp[new_state_tuple] + count) % MOD

                dp = new_dp

            total_subsets = sum(dp.values()) % MOD
            F = (total_subsets - 1) % MOD  # exclude empty subset

        total = (total + sign * F) % MOD

    answer = (total * pow2T) % MOD
    print(answer if answer >= 0 else answer + MOD)

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