結果

問題 No.2959 Dolls' Tea Party
ユーザー lam6er
提出日時 2025-04-16 00:04:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,611 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 157,380 KB
最終ジャッジ日時 2025-04-16 00:06:01
合計ジャッジ時間 6,664 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    # Precompute factorial and inverse factorial up to 1300
    max_m = K
    fact = [1] * (max_m + 1)
    for i in range(1, max_m + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_m + 1)
    inv_fact[max_m] = pow(fact[max_m], MOD-2, MOD)
    for i in range(max_m-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    # Precompute phi for all numbers up to K
    max_phi = K
    phi = list(range(max_phi + 1))
    for p in range(2, max_phi + 1):
        if phi[p] == p:
            for multiple in range(p, max_phi + 1, p):
                phi[multiple] = phi[multiple] // p * (p - 1)
    
    # Function to get all divisors of K
    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)
    
    total = 0
    for d in divisors:
        m = K // d
        if m == 0:
            continue
        
        B = [a // d for a in A]
        k = 0
        S = []
        for i in range(N):
            if B[i] >= m:
                k += 1
            else:
                S.append(B[i])
        
        # Compute e^{kx} mod x^{m+1}
        e_kx = [0] * (m + 1)
        for c in range(m + 1):
            e_kx[c] = pow(k, c, MOD) * inv_fact[c] % MOD
        
        # Compute product of polynomials for S
        dp = [0] * (m + 1)
        dp[0] = 1
        for b in S:
            max_c = min(b, m)
            poly = [inv_fact[c] for c in range(max_c + 1)]
            new_dp = [0] * (m + 1)
            for i in range(m + 1):
                if dp[i] == 0:
                    continue
                for c in range(0, max_c + 1):
                    if i + c > m:
                        break
                    new_dp[i + c] = (new_dp[i + c] + dp[i] * poly[c]) % MOD
            dp = new_dp
        
        # Multiply by e_kx
        final = [0] * (m + 1)
        for i in range(m + 1):
            if dp[i] == 0:
                continue
            for j in range(m + 1 - i):
                final[i + j] = (final[i + j] + dp[i] * e_kx[j]) % MOD
        
        coeff = final[m]
        ways = coeff * fact[m] % MOD
        total = (total + ways * phi[d]) % MOD
    
    inv_K = pow(K, MOD-2, MOD)
    ans = total * inv_K % MOD
    print(ans)

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