結果

問題 No.2243 Coaching Schedule
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:19:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,160 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 116,184 KB
最終ジャッジ日時 2025-06-12 13:22:15
合計ジャッジ時間 6,373 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    from collections import defaultdict

    M, N = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    freq = defaultdict(int)
    for a in A:
        freq[a] += 1
    c = list(freq.values())
    if not c:
        print(0)
        return
    
    max_c = max(c)
    max_n = max(N, max_c)
    
    # Precompute factorial and inverse factorial
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    ans = 0
    # Precompute all possible K - c_s for each c in c
    # To optimize, precompute the required terms for each K
    for K in range(max_c, N + 1):
        # Compute product of P(K, c_s) for all s
        product_p = 1
        for x in c:
            if K < x:
                product_p = 0
                break
            product_p = product_p * fact[K] % MOD
            product_p = product_p * inv_fact[K - x] % MOD
        if product_p == 0:
            continue
        
        # Compute inclusion-exclusion sum for this K
        sum_ie = 0
        for d in range(0, K + 1):
            t = K - d
            valid = True
            for x in c:
                if t < x:
                    valid = False
                    break
            if not valid:
                continue
            
            # Compute combination C(K, d)
            comb = fact[K] * inv_fact[d] % MOD
            comb = comb * inv_fact[K - d] % MOD
            
            # Compute product of P(t, c_s)
            product_t = 1
            for x in c:
                product_t = product_t * fact[t] % MOD
                product_t = product_t * inv_fact[t - x] % MOD
            
            term = comb * product_t % MOD
            if d % 2 == 1:
                term = (-term) % MOD
            sum_ie = (sum_ie + term) % MOD
        
        ans = (ans + sum_ie) % MOD
    
    print(ans)

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