#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int M = 1000007;
int add(int a, int b) {
a += b;
if (a >= M) return a - M;
if (a < 0) return a + M;
return a;
}
int mul(int a, int b) {
return a * (ll) b % M;
}
void addup(int &a, int b) {
a = add(a, b);
}
void mulup(int &a, int b) {
a = mul(a, b);
}
const int N = 10000 + 7;
int n, a[N], mx[N], ways[N];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mx[i] = max(mx[i - 1], a[i]);
ways[i] = 1;
}
int sol = 1;
for (int i = n; i >= 1; i--) {
addup(sol, mul(a[i] - 1, ways[mx[i - 1]]));
for (int j = 1; j <= n - i + 1; j++) {
ways[j] = add(mul(j, ways[j]), ways[j + 1]);
}
}
cout << sol << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
418 ms |
420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
108 ms |
388 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
437 ms |
420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |