結果

問題 No.2243 Coaching Schedule
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:57:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,254 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 121,200 KB
最終ジャッジ日時 2025-04-09 20:59:08
合計ジャッジ時間 6,252 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    M = int(data[0])
    N = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    from collections import defaultdict
    freq = defaultdict(int)
    for a in A:
        freq[a] += 1
    
    max_c = max(freq.values()) if freq else 0
    if max_c == 0:
        print(0)
        return
    
    c_counts = list(freq.values())
    c_facts = [1] * (max_c + 1)
    for i in range(1, max_c + 1):
        c_facts[i] = c_facts[i-1] * i % MOD
    
    product_c_fact = 1
    for cnt in c_counts:
        product_c_fact = product_c_fact * c_facts[cnt] % MOD
    
    max_K = N
    fact = [1] * (max_K + 1)
    inv_fact = [1] * (max_K + 1)
    for i in range(1, max_K + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact[max_K] = pow(fact[max_K], MOD-2, MOD)
    for i in range(max_K-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    ans = 0
    max_c_val = max_c
    for K in range(max_c_val, N + 1):
        product = 1
        possible = True
        for cnt in c_counts:
            if K < cnt:
                possible = False
                break
            c = cnt
            comb = fact[K] * inv_fact[c] % MOD
            comb = comb * inv_fact[K - c] % MOD
            product = product * comb % MOD
        if not possible:
            continue
        
        sum_ie = 0
        for d in range(0, K + 1):
            t = K - d
            valid = True
            product_t = 1
            for cnt in c_counts:
                c = cnt
                if t < c:
                    valid = False
                    break
                comb = fact[t] * inv_fact[c] % MOD
                comb = comb * inv_fact[t - c] % MOD
                product_t = product_t * comb % MOD
            if not valid:
                continue
            sign = (-1) ** d
            comb_kd = fact[K] * inv_fact[d] % MOD
            comb_kd = comb_kd * inv_fact[K - d] % MOD
            term = sign * comb_kd * product_t % MOD
            sum_ie = (sum_ie + term) % MOD
        
        contribution = sum_ie * product_c_fact % MOD
        ans = (ans + contribution) % MOD
    
    print(ans % MOD)

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