#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(1E6) + 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 = 1000 + 5;
int N;
int A[max_N];
int mxc[max_N], usedc[max_N], visc[max_N];
Z pascal[max_N][max_N];
Z binom(int n, int r) {
return pascal[n][r];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
pascal[0][0] = 1;
for (int i = 1; i < max_N; ++i) {
pascal[i][0] = 1;
for (int j = 1; j <= i; ++j) {
pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
}
}
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 += 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4176 KB |
Output is correct |
2 |
Correct |
2 ms |
4348 KB |
Output is correct |
3 |
Correct |
3 ms |
4176 KB |
Output is correct |
4 |
Correct |
2 ms |
4412 KB |
Output is correct |
5 |
Correct |
2 ms |
4176 KB |
Output is correct |
6 |
Correct |
3 ms |
4344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4176 KB |
Output is correct |
2 |
Incorrect |
3 ms |
4176 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4176 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
4176 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4176 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
31 ms |
4176 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
178 ms |
4424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1050 ms |
4176 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4176 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4176 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |