結果

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

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    max_g = K

    # Precompute factorial and inverse factorial up to max_g
    fact = [1] * (max_g + 1)
    for i in range(1, max_g + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_g + 1)
    inv_fact[max_g] = pow(fact[max_g], MOD-2, MOD)
    for i in range(max_g-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    # Precompute combination(m, j) = C(m, j) = fact[m] * inv_fact[j] * inv_fact[m-j] % MOD
    # But for efficiency, compute on the fly using fact and inv_fact

    def comb(m, j):
        if j < 0 or j > m:
            return 0
        return fact[m] * inv_fact[j] % MOD * inv_fact[m - j] % MOD

    # 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)
    divisors.sort()

    # Precompute phi for all possible d = K/g
    # For each d, compute phi(d)
    def compute_phi(max_d):
        phi = list(range(max_d+1))
        for p in range(2, max_d+1):
            if phi[p] == p:  # p is prime
                for multiple in range(p, max_d+1, p):
                    phi[multiple] -= phi[multiple] // p
        return phi

    max_d_for_phi = K
    phi = compute_phi(max_d_for_phi)

    total = 0
    for g in divisors:
        l = K // g
        # For each color, compute m_i = A_i // l
        valid_colors = []
        for a in A:
            mi = a // l
            if mi < 0:
                mi = 0
            ti = min(mi, g)
            if ti >= 0:
                valid_colors.append(ti)
        # Now compute the number of ways to choose c_i for valid_colors with sum c_i = g, c_i <= ti
        # Using the DP approach for multinomial coefficients
        dp = [0] * (g + 1)
        dp[0] = 1
        for ti in valid_colors:
            new_dp = [0] * (g + 1)
            # Compute new_dp[j] = sum_{k=0}^min(ti, j) dp[j -k] * C(j, k)
            for j in range(g + 1):
                if dp[j] == 0:
                    continue
                # k can be from 0 to min(ti, g -j)
                max_k = min(ti, g - j)
                # Iterate k from 0 to max_k
                for k in range(0, max_k + 1):
                    if j + k > g:
                        continue
                    c = comb(j + k, k)
                    new_dp[j + k] = (new_dp[j + k] + dp[j] * c) % MOD
            dp = new_dp
        f_g = dp[g] % MOD
        d = K // g
        ph = phi[d]
        total = (total + f_g * ph) % MOD

    inv_K = pow(K, MOD-2, MOD)
    ans = total * inv_K % MOD
    print(ans)

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