結果

問題 No.2243 Coaching Schedule
ユーザー lam6er
提出日時 2025-03-20 20:49:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,567 bytes
コンパイル時間 360 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 115,588 KB
最終ジャッジ日時 2025-03-20 20:49:15
合計ジャッジ時間 6,761 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    M, N = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))

    from collections import defaultdict
    cnt = defaultdict(int)
    for a in A:
        cnt[a] += 1

    if not cnt:
        print(0)
        return

    max_c = max(cnt.values())
    c = list(cnt.values())
    m = max_c

    # Precompute e_k: e_k is the number of groups with c >k
    e = [0] * m
    for k in range(m):
        for c_i in c:
            if c_i > k:
                e[k] += 1

    # Precompute factorial and inverse factorial
    max_fact = N + m + 2
    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

    # Precompute e_k for log c
    answer = 0
    for K in range(max_c, N+1):
        res = 0
        for d in range(0, K+1):
            x = K - d
            if x < max_c:
                continue
            product = 1
            for k in range(m):
                product = product * pow(x -k, e[k], MOD) % MOD
            # Compute comb(K, d)
            C = fact[K] * inv_fact[d] % MOD * inv_fact[K -d] % MOD
            term = C * product % MOD
            if d % 2 == 1:
                term = (-term) % MOD
            res = (res + term) % MOD
        answer = (answer + res) % MOD

    print(answer % MOD)

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