#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mxn = 10004;
const ll mod = 1000007;
int a[mxn];
int n;
/*
ll dp[mxn][mxn];
ll C(int N, int K){
if(N == 0) return 1;
if(dp[N][K] == -1){
dp[N][K] = C(N-1, K+1) + C(N-1, K)*K;
dp[N][K] %= mod;
}
return dp[N][K];
}*/
int DP1[mxn];
int DP2[mxn];
int main(){
cin >> n;
fr(i, 0, n){
cin >> a[i];
}
int mx[n];
int c = 0;
fr(i, 0, n){
c = max(c, a[i]);
mx[i] = c;
}
ll ans = 1;
fr(i, 0, n+1) DP1[i] = 1;
for(int i = n-1; i >= 0; i --){
int nxt = 1;
if(i > 0) nxt = mx[i-1];
ans += ((a[i]-1) * DP1[nxt]) % mod;
ans %= mod;
fr(j, 0, n+1){
DP2[j] = (DP1[j+1] + j*DP1[j]) % mod;
}
fr(j, 0, n+1){
DP1[j] = DP2[j];
}
}
/*int nxt = 2;
ll ans = 1;
fr(i, 0, n){
int rem = n-i;
ans += ((a[i]-1) * C(rem-1, nxt-1)) % mod;
ans %= mod;
if(a[i] == nxt){
nxt++;
}
}*/
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
304 KB |
Output is correct |
2 |
Correct |
3 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
201 ms |
480 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
59 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
195 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |