結果

問題 No.243 出席番号(2)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:43:17
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,047 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 77,156 KB
最終ジャッジ日時 2025-06-12 16:43:21
合計ジャッジ時間 3,213 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 MLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

MOD = 10**9 + 7

def main():
    N = int(sys.stdin.readline())
    A = [int(sys.stdin.readline()) for _ in range(N)]
    
    freq = defaultdict(int)
    for a in A:
        freq[a] += 1
    
    # Compute the generating function
    gf = [1]
    for v in freq:
        m = freq[v]
        new_gf = [0] * (len(gf) + 1)
        for k in range(len(gf)):
            new_gf[k] = (new_gf[k] + gf[k]) % MOD
            new_gf[k+1] = (new_gf[k+1] + gf[k] * m) % MOD
        gf = new_gf
    
    # Precompute factorials
    fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = fact[i-1] * i % MOD
    
    # Compute the inclusion-exclusion sum
    ans = 0
    for k in range(len(gf)):
        fk = gf[k]
        if fk == 0:
            continue
        rem = N - k
        if rem < 0:
            continue
        term = fk * fact[rem] % MOD
        if k % 2 == 1:
            term = (-term) % MOD
        ans = (ans + term) % MOD
    print(ans % MOD)

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