結果
問題 |
No.243 出席番号(2)
|
ユーザー |
👑 |
提出日時 | 2022-11-03 00:06:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 754 bytes |
コンパイル時間 | 3,129 ms |
コンパイル使用メモリ | 254,668 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-17 11:48:52 |
合計ジャッジ時間 | 4,685 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/modint> using namespace std; using namespace atcoder; using mint = modint1000000007; void solve(){ int n; cin >> n; map<int, int> cnt; int a; for(int i = 0; i < n; i++){ cin >> a; if(a < n) cnt[a]++; } vector<mint> dp(n + 1, 0); dp[0] = 1; for(auto tmp:cnt){ int v = tmp.second; for(int i = n; i > 0; i--) dp[i] += dp[i - 1] * v; } vector<mint> fact(n + 1); fact[0] = 1; for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i; mint ans = 0; mint pm = 1; for(int i = 0; i <= n; i++){ ans += pm * dp[i] * fact[n - i]; pm *= -1; } cout << ans.val() << "\n"; } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); }