#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
template<typename T>
T power(T a, i64 b) {
T res = 1;
while(b) {
if(b & 1) {
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
constexpr int md = int(1E9) + 7;
struct MInt {
int val;
MInt() : val(0) {}
template<typename T>
MInt(T v) {
if(-md <= v && v < md) {
val = v;
} else {
val = v % md;
}
if(val < 0) {
val += md;
}
}
int operator() () { return val; }
MInt operator+= (MInt rhs) {
if((val += rhs.val) >= md) {
val -= md;
}
return *this;
}
MInt operator-= (MInt rhs) {
if((val -= rhs.val) < 0) {
val += md;
}
return *this;
}
MInt operator*= (MInt rhs) {
val = (int)(1LL * val * rhs.val % md);
return *this;
}
MInt inv() {
return power(*this, md - 2);
}
MInt operator/= (MInt rhs) {
return *this *= rhs.inv();
}
bool operator== (MInt rhs) {
return val == rhs.val;
}
bool operator!= (MInt rhs) {
return val != rhs.val;
}
};
MInt operator+ (MInt lhs, MInt rhs) {
return lhs += rhs;
}
MInt operator- (MInt lhs, MInt rhs) {
return lhs -= rhs;
}
MInt operator* (MInt lhs, MInt rhs) {
return lhs *= rhs;
}
MInt operator/ (MInt lhs, MInt rhs) {
return lhs /= rhs;
}
std::ostream& operator<< (std::ostream& os, MInt v) {
return os << v();
}
std::string to_string(MInt x) {
return to_string(x());
}
using Z = MInt;
constexpr int max_N = 100 + 5;
int N;
int A[max_N];
int mxc[max_N], usedc[max_N], visc[max_N];
struct Comb {
int n;
std::vector<Z> _fac, _inv_fac, _inv;
Comb() : n{0}, _fac{1}, _inv_fac{1}, _inv{0} {}
Comb(int _n) : Comb() {
init(_n);
}
void init(int m) {
_fac.resize(m + 1);
_inv_fac.resize(m + 1);
_inv.resize(m + 1);
for(int i = n + 1; i <= m; ++i) {
_fac[i] = _fac[i - 1] * i;
}
_inv_fac[m] = _fac[m].inv();
for(int i = m; i > n; --i) {
_inv_fac[i - 1] = _inv_fac[i] * i;
_inv[i] = _inv_fac[i] * _fac[i - 1];
}
n = m;
}
Z fac(int m) {
if(m > n) init(2 * m);
return _fac[m];
}
Z inv_fac(int m) {
if(m > n) init(2 * m);
return _inv_fac[m];
}
Z inv(int m) {
if(m > n) init(2 * m);
return _inv[m];
}
Z binom(int m, int r) {
if(m < r || r < 0) return 0;
return fac(m) * inv_fac(m - r) * inv_fac(r);
}
} comb;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N;
for (int i = 1; i <= N; ++i) {
std::cin >> A[i];
}
Z ans = 1;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j < A[i]; ++j) {
int gap = N - i;
int had = usedc[i - 1] + !visc[j];
for (int k = std::max(mxc[i - 1], j); k <= N; ++k) {
int need = k - had;
if (need <= gap) {
ans += comb.binom(gap, need) * power(Z(k), gap - need);
}
}
}
mxc[i] = std::max(mxc[i - 1], A[i]);
usedc[i] = usedc[i - 1] + !visc[A[i]];
visc[A[i]] = true;
}
bool good = true;
for (int i = 1; i <= mxc[i]; ++i) {
good &= visc[i];
}
if (good) {
std::cout << ans << '\n';
} else {
std::cout << "0\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
