結果

問題 No.243 出席番号(2)
ユーザー tkmst201tkmst201
提出日時 2020-11-13 10:48:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 3,837 bytes
コンパイル時間 2,024 ms
コンパイル使用メモリ 202,260 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-30 01:57:39
合計ジャッジ時間 3,947 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 4 ms
4,376 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 4 ms
4,376 KB
testcase_06 AC 4 ms
4,380 KB
testcase_07 AC 4 ms
4,376 KB
testcase_08 AC 11 ms
4,376 KB
testcase_09 AC 11 ms
4,376 KB
testcase_10 AC 11 ms
4,376 KB
testcase_11 AC 11 ms
4,380 KB
testcase_12 AC 11 ms
4,380 KB
testcase_13 AC 22 ms
4,376 KB
testcase_14 AC 22 ms
4,380 KB
testcase_15 AC 22 ms
4,380 KB
testcase_16 AC 22 ms
4,376 KB
testcase_17 AC 22 ms
4,376 KB
testcase_18 AC 37 ms
4,376 KB
testcase_19 AC 37 ms
4,376 KB
testcase_20 AC 38 ms
4,376 KB
testcase_21 AC 38 ms
4,376 KB
testcase_22 AC 38 ms
4,376 KB
testcase_23 AC 58 ms
4,376 KB
testcase_24 AC 57 ms
4,376 KB
testcase_25 AC 58 ms
4,376 KB
testcase_26 AC 58 ms
4,380 KB
testcase_27 AC 58 ms
4,380 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

/*
P_i := i 君に出席番号 A_i が割り振られる事象
(\bigcup_{i=0}^N P_i)^c が答え(^c は補集合)
包除原理で求める

同じ A_i を持つような i から(2 つ以上)適当に選び b_1, b_2 , .., b_m とすると、
 \bigcap_{j=0}^m P_j = \emptyset
なので、同じ A_i を持つ人をまとめる

dp[i][j] :=
	A_i <= i を持つ人までで次の条件を満たす k の個数が j であるような選び方
	- 同じ A_k を持つような k は 1 つのみ
*/

template<int M>
struct ModInt {
public:
	using value_type = long long;
	
	ModInt(value_type val = 0) : val(val < 0 ? (M - (-val % M)) % M : val % M) {}
	
	explicit operator bool() const noexcept { return val; }
	bool operator ==(const ModInt & rhs) const noexcept { return val == rhs.val; }
	bool operator !=(const ModInt & rhs) const noexcept { return !(*this == rhs); }
	ModInt operator +() const noexcept { return ModInt(*this); }
	ModInt operator -() const noexcept { return ModInt(0) -= *this; }
	ModInt operator +(const ModInt & rhs) const noexcept { return ModInt(*this) += rhs; }
	ModInt operator -(const ModInt & rhs) const noexcept { return ModInt(*this) -= rhs; }
	ModInt operator *(const ModInt & rhs) const noexcept { return ModInt(*this) *= rhs; }
	ModInt operator /(const ModInt & rhs) const noexcept { return ModInt(*this) /= rhs; }
	
	ModInt & operator +=(const ModInt & rhs) noexcept {
		val += rhs.val;
		if (val >= M) val -= M;
		return *this;
	}
	ModInt & operator -=(const ModInt & rhs) noexcept {
		if (val < rhs.val) val += M;
		val -= rhs.val;
		return *this;
	}
	ModInt & operator *=(const ModInt & rhs) noexcept {
		val = val * rhs.val % M;
		return *this;
	}
	ModInt & operator /=(const ModInt & rhs) noexcept {
		*this *= rhs.inverse();
		return *this;
	}
	
	ModInt pow(value_type n) const {
		ModInt res = 1, x = val;
		if (n < 0) { x = x.inverse(); n = -n; }
		while (n) { if (n & 1) res *= x; x *= x; n >>= 1; }
		return res;
	}
	
	ModInt inverse() const {
		long long a = val, a1 = 1, a2 = 0, b = M, b1 = 0, b2 = 1;
		while (b > 0) {
			value_type q = a / b, r = a % b;
			value_type nb1 = a1 - q * b1, nb2 = a2 - q * b2;
			a = b; b = r;
			a1 = b1; b1 = nb1;
			a2 = b2; b2 = nb2;
		}
		assert(a == 1);
		return a1;
	}
	
	const value_type & get() const noexcept { return val; }
	static decltype(M) get_mod() noexcept { return M; }
	
	friend std::ostream & operator <<(std::ostream & os, const ModInt & rhs) { return os << rhs.val; }
	friend std::istream & operator >>(std::istream & is, ModInt & rhs) {
		value_type x;
		is >> x;
		rhs = ModInt(x);
		return is;
	}
private:
	value_type val;
};
using mint = ModInt<MOD>;

int main() {
	int N;
	cin >> N;
	vector<int> A(N), cnt(5000);
	REP(i, N) scanf("%d", &A[i]), ++cnt[A[i]];
	
	/*
	dp[i][j] :=
	A_i <= i を持つ人までで次の条件を満たす k の個数が j であるような選び方
	- 同じ A_k を持つような k は 1 つのみ
	*/
	vector<mint> dp(N + 1);
	dp[0] = 1;
	REP(i, N) for (int j = N - 1; j >= 0; --j) dp[j + 1] += dp[j] * cnt[i];
	
	vector<mint> fact(N + 1);
	fact[0] = 1;
	FOR(i, 1, N + 1) fact[i] = fact[i - 1] * i;
	
	mint ans = 0;
	REP(i, N + 1) {
		mint cur = dp[i] * fact[N - i];
		ans += cur * ((i & 1) ? -1 : 1);
	}
	
	cout << ans << endl;
	
	return 0;
}
0