結果
| 問題 | No.243 出席番号(2) |
| ユーザー |
 yukinon0808
|
| 提出日時 | 2020-04-14 17:26:01 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 160 ms / 2,000 ms |
| コード長 | 6,870 bytes |
| コンパイル時間 | 1,850 ms |
| コンパイル使用メモリ | 182,372 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-01 17:18:20 |
| 合計ジャッジ時間 | 3,518 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<class T>bool chmax(T& a, const T& b) {if (a < b) { a = b; return true; }return false;}template<class T>bool chmin(T& a, const T& b) {if (b < a) { a = b; return true; }return false;}// std::vector Declarationtemplate<typename T>vector<T> make_v(size_t a) { return vector<T>(a); }template<typename T, typename... Ts>auto make_v(size_t a, Ts... ts) {return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));}// std::vector Declaration and Initializationtemplate<typename T>vector<T> make_vector(size_t a, T x) { return vector<T>(a, x); }template<typename T, typename U, typename... Ts>auto make_vector(size_t a, U b, Ts... ts) {return vector<decltype(make_vector<T>(b,ts...))>(a, make_vector<T>(b, ts...));}// std::vector Inputtemplate<typename T>istream& operator>>(istream& is, vector<T>& v) {for (auto &e : v) is >> e;return is;}// std::vector Debugtemplate<typename T>ostream& operator<<(ostream& os, const vector<T>& v) {os << "[";bool a = 1;for (auto e : v) {os << (a ? "" : " ");os << e;a = 0;}os << "]";return os;}// std::array Debugtemplate<typename T, size_t n>ostream& operator<<(ostream& os, const array<T, n>& v) {os << "[";bool a = 1;for (auto e : v) {os << (a ? "" : " ");os << e;a = 0;}os << "]";return os;}// std::deque Debugtemplate<typename T>ostream& operator<<(ostream& os, const deque<T>& d) {os << "[";bool a = 1;for (auto e : d) {os << (a ? "" : " ");os << e;a = 0;}os << "]";return os;}// std::pair Debugtemplate<typename T, typename U>ostream& operator<<(ostream& os, const pair<T, U>& p) {os << "(" << p.first << " " << p.second << ")";return os;}// std::set Debugtemplate<typename T>ostream& operator<<(ostream& os, const set<T>& st) {os << "{";bool a = 1;for (auto e : st) {os << (a ? "" : " ");os << e;a = 0;}os << "}";return os;}// std::multiset Debugtemplate<typename T>ostream& operator<<(ostream& os, const multiset<T>& st) {os << "{";bool a = 1;for (auto e : st) {os << (a ? "" : " ");os << e;a = 0;}os << "}";return os;}// std::map Debugtemplate<typename T, typename U>ostream& operator<<(ostream& os, const map<T, U>& mp) {os << "{";bool a = 1;for (auto e : mp) {os << (a ? "" : " ");os << e.first << ":" << e.second;a = 0;}os << "}";return os;}// std::tuple Debugtemplate<int N, class Tuple>void out(ostream& os, const Tuple& t){}template<int N, class Tuple, class H, class ...Ts>void out(ostream& os, const Tuple& t) {if (N) os << " ";os << get<N>(t);out<N+1,Tuple,Ts...>(os, t);}template<class ...Ts>ostream& operator<<(ostream& os, const tuple<Ts...>& t) {os << "(";out<0,tuple<Ts...>,Ts...>(os, t);os << ")";return os;}// Debug#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl// Weighted edgetemplate<typename T>struct edge {int src, to;T cost;edge() {}edge(int to, T cost) : src(-1), to(to), cost(cost) {}edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}friend ostream& operator<<(ostream& os, const edge& e) {return os << "(" << e.src << "->" << e.to << ":" << e.cost << ")";}};using LL = int64_t;#define fs first#define sc secondtemplate<int64_t mod>struct modint {using LL = int64_t;LL val;modint(LL val=0) : val(((val % mod) + mod) % mod) {}const modint operator+() const { return *this; }const modint operator-() const { return (-val + mod) % mod; }const modint inv() const { return pow(mod-2); }modint& operator+=(const modint& rhs) {(val += rhs.val) %= mod;return *this;}modint& operator-=(const modint& rhs) {return *this += -rhs;}modint& operator*=(const modint& rhs) {(val *= rhs.val) %= mod;return *this;}modint& operator/=(const modint& rhs) {return *this *= rhs.inv();}const modint operator+(const modint& rhs) const {return modint(*this) += rhs;}const modint operator-(const modint& rhs) const {return modint(*this) -= rhs;}const modint operator*(const modint& rhs) const {return modint(*this) *= rhs;}const modint operator/(const modint& rhs) const {return modint(*this) /= rhs;}const modint pow(LL n) const {modint ret = 1, tmp = val;while (n > 0) {if (n & 1) ret *= tmp;tmp *= tmp; n >>= 1;}return ret;}bool operator==(const modint& rhs) const { return val == rhs.val; }bool operator!=(const modint& rhs) const { return !(*this == rhs); }friend const modint operator+(const LL& lhs, const modint& rhs) {return modint(lhs) + rhs;}friend const modint operator-(const LL& lhs, const modint& rhs) {return modint(lhs) - rhs;}friend const modint operator*(const LL& lhs, const modint& rhs) {return modint(lhs) * rhs;}friend const modint operator/(const LL& lhs, const modint& rhs) {return modint(lhs) / rhs;}friend bool operator==(const LL& lhs, const modint& rhs) {return modint(lhs) == rhs;}friend bool operator!=(const LL& lhs, const modint& rhs) {return modint(lhs) != rhs;}friend ostream& operator<<(ostream& os, const modint& a) {return os << a.val;}friend istream& operator>>(istream& is, modint& a) {LL tmp; is >> tmp;a = tmp;return is;}};const int64_t MOD = 1e9+7;using Int = modint<MOD>;int main(){cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(10);int n; cin >> n;map<int,LL> cnt;for (int i = 0; i < n; ++i) {int a; cin >> a;if (a >= n) continue;++cnt[a];}vector<LL> b;for (const auto& tp : cnt) b.push_back(tp.second);int m = b.size();auto dp = make_v<Int>(2, n+1);dp[0][0] = 1;for (int i = 0; i < m; ++i) {dp[(i+1) & 1].assign(n+1, 0);for (int j = 0; j <= n; ++j) {dp[(i+1) & 1][j] += dp[i & 1][j];if (j < n) dp[(i+1) & 1][j+1] += dp[i & 1][j] * b[i];}}vector<Int> fact(n+1);fact[0] = 1;for (int i = 1; i <= n; ++i) {fact[i] = fact[i-1] * i;}Int ans = 0;for (int k = 0; k <= n; ++k) {ans += dp[m & 1][k] * fact[n-k] * (k & 1 ? -1 : 1);}cout << ans << endl;return 0;}