oj.uz

답안 #212293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
212293 2020-03-22T16:41:30 Z ksun48 유적 3 (JOI20_ruins3) C++14
100 / 100
 1835 ms 10476 KB 
#include <bits/stdc++.h>
using namespace std;

template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");

private:
	using ll = long long;

	int v;

	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}

public:

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	friend modnum inv(const modnum& m) { return m.inv(); }
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	friend modnum neg(const modnum& m) { return m.neg(); }

	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}

	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}

	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

template <typename T> T pow(T a, long long b) {
	assert(b >= 0);
	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

using num = modnum<int(1e9) + 7>;

vector<num> fact, ifact;

void init(){
	int N = 1100000;
	fact = {1};
	for(int i = 1; i < N; i++) fact.push_back(i * fact[i-1]);
	ifact.resize(N);
	ifact.back() = 1 / fact.back();
	for(int i = N - 1; i > 0; i--) ifact[i-1] = i * ifact[i];
}

num ncr(int n, int k){
	if(k < 0 || k > n) return 0;
	return fact[n] * ifact[k] * ifact[n-k];
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	init();
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
	}
	vector<vector<num> > dp(n+1, vector<num>(n+1, 0));
	dp[n][0] = 1;
	for(int j = n-1; j >= 0; j--){
		for(int prev_used = 0; prev_used < n-j; prev_used++){
			num F = 0;
			for(int k = j+1; k <= n; k++) F += dp[k][prev_used];
			for(int cur = 1; cur + prev_used <= n-j; cur++){
				if(F == 0) continue;
				num ways = fact[cur] * fact[cur-1];
				ways *= ncr(2*cur, cur);
				dp[j][cur + prev_used] += F * ncr(n - j - prev_used - 1, cur - 1) * ncr(a[j] - j - n + prev_used + cur, cur) * ways;
			}
		}
	}
	cout << dp[0][n] / pow(num(2), n) << '\n';
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 9196 KB Output is correct
2 Correct 28 ms 9068 KB Output is correct
3 Correct 28 ms 9068 KB Output is correct
4 Correct 28 ms 9068 KB Output is correct
5 Correct 28 ms 9068 KB Output is correct
6 Correct 28 ms 9068 KB Output is correct
7 Correct 28 ms 9068 KB Output is correct
8 Correct 31 ms 9068 KB Output is correct
9 Correct 28 ms 9068 KB Output is correct
10 Correct 29 ms 9068 KB Output is correct

Subtask #2
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 9196 KB Output is correct
2 Correct 28 ms 9068 KB Output is correct
3 Correct 28 ms 9068 KB Output is correct
4 Correct 28 ms 9068 KB Output is correct
5 Correct 28 ms 9068 KB Output is correct
6 Correct 28 ms 9068 KB Output is correct
7 Correct 28 ms 9068 KB Output is correct
8 Correct 31 ms 9068 KB Output is correct
9 Correct 28 ms 9068 KB Output is correct
10 Correct 29 ms 9068 KB Output is correct
11 Correct 30 ms 9068 KB Output is correct
12 Correct 29 ms 9064 KB Output is correct
13 Correct 29 ms 9068 KB Output is correct
14 Correct 29 ms 9068 KB Output is correct
15 Correct 29 ms 9068 KB Output is correct
16 Correct 32 ms 9068 KB Output is correct
17 Correct 28 ms 9068 KB Output is correct
18 Correct 30 ms 9068 KB Output is correct
19 Correct 30 ms 9100 KB Output is correct
20 Correct 30 ms 9068 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 9196 KB Output is correct
2 Correct 28 ms 9068 KB Output is correct
3 Correct 28 ms 9068 KB Output is correct
4 Correct 28 ms 9068 KB Output is correct
5 Correct 28 ms 9068 KB Output is correct
6 Correct 28 ms 9068 KB Output is correct
7 Correct 28 ms 9068 KB Output is correct
8 Correct 31 ms 9068 KB Output is correct
9 Correct 28 ms 9068 KB Output is correct
10 Correct 29 ms 9068 KB Output is correct
11 Correct 30 ms 9068 KB Output is correct
12 Correct 29 ms 9064 KB Output is correct
13 Correct 29 ms 9068 KB Output is correct
14 Correct 29 ms 9068 KB Output is correct
15 Correct 29 ms 9068 KB Output is correct
16 Correct 32 ms 9068 KB Output is correct
17 Correct 28 ms 9068 KB Output is correct
18 Correct 30 ms 9068 KB Output is correct
19 Correct 30 ms 9100 KB Output is correct
20 Correct 30 ms 9068 KB Output is correct
21 Correct 1325 ms 10468 KB Output is correct
22 Correct 1282 ms 10464 KB Output is correct
23 Correct 1312 ms 10460 KB Output is correct
24 Correct 1257 ms 10468 KB Output is correct
25 Correct 186 ms 10464 KB Output is correct
26 Correct 1259 ms 10460 KB Output is correct
27 Correct 187 ms 10468 KB Output is correct
28 Correct 1290 ms 10468 KB Output is correct
29 Correct 190 ms 10340 KB Output is correct
30 Correct 1835 ms 10476 KB Output is correct
31 Correct 1607 ms 10476 KB Output is correct
32 Correct 1775 ms 10464 KB Output is correct
33 Correct 1805 ms 10464 KB Output is correct
34 Correct 1638 ms 10460 KB Output is correct
35 Correct 1802 ms 10464 KB Output is correct
36 Correct 1797 ms 10464 KB Output is correct