結果

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

ソースコード

diff #
raw source code 

MOD = 10**9 + 7

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

from collections import defaultdict
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1

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

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

# Process each unique disliked number
for x in cnt:
    k = cnt[x]
    if k == 0:
        continue
    tmp = [0] * (N + 1)
    for m in range(N + 1):
        if dp[m] == 0:
            continue
        # Do not choose x
        tmp[m] = (tmp[m] + dp[m]) % MOD
        # Choose one occurrence of x
        if m + 1 <= N:
            tmp[m+1] = (tmp[m+1] + dp[m] * (-k)) % MOD
    dp = tmp

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

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