#578985 (C++17) No.243 出席番号(2)

提出ソース

結果

問題	No.243 出席番号(2)
ユーザー	tkmst201
提出日時	2020-11-13 10:39:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	5,104 bytes
コンパイル時間	2,586 ms
コンパイル使用メモリ	207,980 KB
実行使用メモリ	199,264 KB
最終ジャッジ日時	2023-09-30 01:57:29
合計ジャッジ時間	6,730 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	11 ms 11,432 KB
testcase_04	AC	12 ms 11,288 KB
testcase_05	AC	11 ms 11,388 KB
testcase_06	AC	11 ms 11,296 KB
testcase_07	AC	11 ms 11,548 KB
testcase_08	AC	39 ms 34,964 KB
testcase_09	AC	40 ms 34,936 KB
testcase_10	AC	40 ms 34,844 KB
testcase_11	AC	40 ms 34,932 KB
testcase_12	RE	-
testcase_13	MLE	-
testcase_14	MLE	-
testcase_15	MLE	-
testcase_16	MLE	-
testcase_17	RE	-
testcase_18	MLE	-
testcase_19	MLE	-
testcase_20	MLE	-
testcase_21	MLE	-
testcase_22	RE	-
testcase_23	MLE	-
testcase_24	MLE	-
testcase_25	MLE	-
testcase_26	MLE	-
testcase_27	MLE	-
testcase_28	AC	2 ms 4,376 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	1 ms 4,376 KB
testcase_31	AC	2 ms 4,380 KB
testcase_32	AC	1 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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>;

template<typename T>
struct Combination {
public:
	using size_type = std::size_t;
	
	Combination(size_type sz = 1) : _fact(1, 1), _finv(1, 1), _inv(1, 1) { build(sz); }
	
	T fact(size_type k) { if (k >= T::get_mod()) return 0; build(k); return _fact[k]; }
	T finv(size_type k) { assert(k < T::get_mod()); build(k); return _finv[k]; }
	T inv(size_type k) { assert(k > 0 && k < T::get_mod()); build(k); return _inv[k]; }
	
	T operator ()(int n, int r) { return c(n, r); }
	T c(int n, int r) {
		if (r < 0 || n < r) return 0;
		return fact(n) * finv(r) * finv(n - r);
	}
	
private:
	std::vector<T> _fact, _finv, _inv;
	static constexpr size_type MAX_LIMIT = 50000000;
	
	void build(size_type k) {
		if (_fact.size() > k) return;
		assert(k < MAX_LIMIT);
		size_type sz = std::min({MAX_LIMIT, static_cast<size_type>(T::get_mod()), std::max(_fact.size() * 2, k + 1)});
		size_type presz = _fact.size();
		_fact.resize(sz);
		_finv.resize(sz);
		_inv.resize(sz);
		
		for (size_type i = presz; i < sz; ++i) _fact[i] = _fact[i - 1] * i;
		_finv[sz - 1] = T(_fact[sz - 1]).inverse();
		for (size_type i = sz - 1; i > presz; --i) {
			_finv[i - 1] = _finv[i] * i;
			_inv[i] = _fact[i - 1] * _finv[i];
		}
		_inv[presz] = _fact[presz - 1] * _finv[presz];
	}
};
using Comb = Combination<mint>;
Comb comb;

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

yukicoder

結果

テストケース

ソースコード