結果

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

ソースコード

diff #
raw source code 

MOD = 10**9 + 7

n = int(input())
cnt = [0] * 5000  # Since A_i can be up to 4999
for _ in range(n):
    a = int(input())
    cnt[a] += 1

# Initialize DP
dp = [0] * (n + 1)
dp[0] = 1

for x in range(5000):
    current_cnt = cnt[x]
    if current_cnt == 0:
        continue
    new_dp = [0] * (n + 1)
    for k in range(n + 1):
        if dp[k] == 0:
            continue
        # Do not choose any student with A_i = x
        new_dp[k] = (new_dp[k] + dp[k]) % MOD
        # Choose one student with A_i = x
        if k + 1 <= n:
            new_dp[k + 1] = (new_dp[k + 1] + dp[k] * current_cnt) % MOD
    dp = new_dp

# Precompute factorials
fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % MOD

ans = 0
for k in range(n + 1):
    if dp[k] == 0:
        continue
    term = dp[k] * fact[n - k] % MOD
    if k % 2 == 1:
        term = (-term) % MOD
    ans = (ans + term) % MOD

print(ans)
0