結果
問題 |
No.243 出席番号(2)
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:25:17 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,158 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 82,844 KB |
実行使用メモリ | 77,944 KB |
最終ジャッジ日時 | 2025-03-31 17:25:34 |
合計ジャッジ時間 | 3,964 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 MLE * 25 |
ソースコード
mod = 10**9 + 7 N = int(input()) A = [int(input()) for _ in range(N)] from collections import defaultdict # Count the occurrences of each disliked number cnt = defaultdict(int) for a in A: cnt[a] += 1 # List of unique disliked numbers that appear at least once vals = list(cnt.keys()) # Precompute factorial modulo mod fact = [1] * (N + 1) for i in range(1, N + 1): fact[i] = fact[i - 1] * i % mod # Initialize DP: dp[k] is the number of ways to choose k distinct values dp = [0] * (N + 1) dp[0] = 1 for v in vals: c = cnt[v] # Update dp in reverse to avoid overwriting values we still need to process for j in range(N, -1, -1): if dp[j] and j < N: dp[j + 1] = (dp[j + 1] + dp[j] * c) % mod # Calculate the result using inclusion-exclusion principle result = 0 for k in range(0, N + 1): if dp[k] == 0: continue remaining = N - k if remaining < 0: continue # Current term: (-1)^k * dp[k] * (remaining)! term = dp[k] * fact[remaining] % mod if k % 2 == 1: term = (mod - term) % mod # Convert to positive mod value result = (result + term) % mod print(result)