結果

問題 No.2959 Dolls' Tea Party
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:53:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,182 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 167,328 KB
最終ジャッジ日時 2025-06-12 13:55:37
合計ジャッジ時間 6,257 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, K = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    
    max_fact = K
    fact = [1] * (max_fact + 1)
    for i in range(1, max_fact + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_fact + 1)
    inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD)
    for i in range(max_fact-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    def get_divisors(n):
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(divisors)
    
    divisors = get_divisors(K)
    
    def euler_phi(n):
        result = n
        i = 2
        while i * i <= n:
            if n % i == 0:
                while n % i == 0:
                    n //= i
                result -= result // i
            i += 1
        if n > 1:
            result -= result // n
        return result
    
    total = 0
    for d in divisors:
        t = K // d
        m_count = 0
        group2 = []
        for a in A:
            m_i = a // t
            c_max = min(m_i, d)
            if c_max >= d:
                m_count += 1
            else:
                group2.append(c_max)
        
        dp = [0] * (d + 1)
        dp[0] = 1
        for c_max in group2:
            new_dp = dp.copy()
            for j in range(d, -1, -1):
                for c in range(1, min(c_max, j) + 1):
                    new_dp[j] = (new_dp[j] + dp[j - c] * inv_fact[c]) % MOD
            dp = new_dp
        
        res = 0
        for c in range(0, d + 1):
            if dp[c] == 0:
                continue
            power = pow(m_count, d - c, MOD)
            comb = fact[d] * inv_fact[d - c] % MOD
            term = dp[c] * power % MOD
            term = term * comb % MOD
            res = (res + term) % MOD
        
        phi_t = euler_phi(t)
        total = (total + res * phi_t) % MOD
    
    ans = total * pow(K, MOD-2, MOD) % MOD
    print(ans)

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