#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 = 200 + 5;
int N;
int A[max_N];
int mxc[max_N], usedc[max_N];
std::map<int, int> visc;
bool vis[max_N][max_N][max_N];
Z dp[max_N][max_N][max_N];
Z f(int x, int y, int z) {
if (x == 0) {
debug(x, y, z, y == z);
return y == z;
} else if (vis[x][y][z]) {
debug(x, y, z, dp[x][y][z]);
return dp[x][y][z];
}
vis[x][y][z] = true;
Z& ans = dp[x][y][z];
ans += f(x - 1, y, z) * z;
ans += f(x - 1, y, z + 1) * (y - z);
debug(x, y, z, ans);
return ans;
}
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 = 0;
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) {
Z x = f(gap, k, had);
debug(i, j, k, gap, had, need, x);
ans += x;
}
}
}
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];
}
ans += good;
std::cout << ans << '\n';
return 0;
}
Compilation message
teams.cpp: In instantiation of 'MInt::MInt(T) [with T = bool]':
teams.cpp:102:21: required from here
teams.cpp:30:16: warning: comparison of constant '-1000007' with boolean expression is always true [-Wbool-compare]
30 | if(-md <= v && v < md) {
| ~~~~^~~~
teams.cpp:30:26: warning: comparison of constant '1000007' with boolean expression is always true [-Wbool-compare]
30 | if(-md <= v && v < md) {
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
35408 KB |
Output is correct |
| 2 |
Correct |
5 ms |
35576 KB |
Output is correct |
| 3 |
Correct |
5 ms |
35408 KB |
Output is correct |
| 4 |
Correct |
5 ms |
35408 KB |
Output is correct |
| 5 |
Correct |
6 ms |
35408 KB |
Output is correct |
| 6 |
Correct |
5 ms |
35576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
35408 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
35408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
36944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
36944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
35408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
35408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
42568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
35408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
