結果

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

ソースコード

diff # 

MOD = 10**9 + 7

N = int(input())
A = [int(input()) for _ in range(N)]

max_k = 5000  # Since A_i can be up to 4999
cnt = [0] * (max_k + 1)
for a in A:
    cnt[a] += 1

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

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

for k in range(max_k + 1):
    c = cnt[k]
    if c == 0:
        continue
    # Create new_dp to store updated values
    new_dp = [0] * (N + 1)
    for m in range(N + 1):
        if dp[m] == 0:
            continue
        # Option 1: do not choose any i with A_i = k
        new_dp[m] = (new_dp[m] + dp[m]) % MOD
        # Option 2: choose one i with A_i = k
        if m + 1 <= N:
            new_dp[m+1] = (new_dp[m+1] + dp[m] * (-c)) % MOD
    dp = new_dp

# Calculate the answer by summing dp[m] * (N - m)!
ans = 0
for m in range(N + 1):
    if N - m >= 0:
        term = (dp[m] * fact[N - m]) % MOD
        ans = (ans + term) % MOD

# Ensure the answer is non-negative
print(ans % MOD)
0