| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 212293 |
2020-03-22T16:41:30 Z |
ksun48 |
Ruins 3 (JOI20_ruins3) |
C++14 |
|
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';
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
