結果

問題 No.2959 Dolls' Tea Party
ユーザー lam6er
提出日時 2025-03-31 17:58:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,944 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 53,532 KB
最終ジャッジ日時 2025-03-31 17:59:02
合計ジャッジ時間 6,372 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+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 euler_phi(m):
        if m == 0:
            return 0
        res = m
        i = 2
        while i * i <= m:
            if m % i == 0:
                while m % i ==0:
                    m //= i
                res -= res //i
            i +=1
        if m >1:
            res -= res //m
        return res
    
    def divisors(n):
        divs = set()
        for i in range(1, int(n**0.5)+1):
            if n %i ==0:
                divs.add(i)
                divs.add(n//i)
        return sorted(divs)
    
    divs = divisors(K)
    
    ans =0
    
    for d in divs:
        if K %d !=0:
            continue
        L = K //d
        
        dp = [0]*(d+1)
        dp[0] =1
        
        for a in A:
            u = a // L
            m_max = min(u, d)
            if m_max ==0:
                continue
            new_dp = [0]*(d+1)
            for s in range(d+1):
                if dp[s] ==0:
                    continue
                for m in range(0, m_max+1):
                    if s +m >d:
                        break
                    new_dp[s +m] = (new_dp[s+m] + dp[s] * inv_fact[m]) % MOD
            dp = new_dp
        
        f_d = dp[d] * fact[d] % MOD
        m = K //d
        phi_val = euler_phi(m)
        ans = (ans + f_d * phi_val) % MOD
    
    inv_K = pow(K, MOD-2, MOD)
    ans = ans * inv_K % MOD
    print(ans)
    
if __name__ == '__main__':
    main()
0