#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 10001;
const ll md = 1e6+7;
ll n, a[MAXN], pt = 0;
ll ans = 0;
map <pair<int,int>,ll> dp;
void get(int sz, int t){
if(dp[{sz,t}]) return;
if(sz==0){
dp[{sz,t}] = 1ll;
return;
}
get(sz-1,t); get(sz-1,t+1);
dp[{sz,t}] = (((ll)t*dp[{sz-1,t}])%md)+dp[{sz-1,t+1}];
dp[{sz,t}] = (dp[{sz,t}]>=md?dp[{sz,t}]-md:dp[{sz,t}]);
/*for(int i = 1; i < MAXN; i++) dp[1][i] = i+1, dp[0][i] = 1ll;
for(ll i = 2; i < MAXN; i++)
for(ll j = 1; j < MAXN; j++){
dp[i][j] = (j*dp[i-1][j])%md;
if(j+1 < MAXN) dp[i][j] += dp[i-1][j+1], dp[i][j] = (dp[i][j]>=md?dp[i][j]-md:dp[i][j]);
}*/
return;
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
pt = 1;
for(int i = 0; i < n; i++){
if(a[i]==1) continue;
ll tmp = (ll)a[i]-1ll;
get(n-i+1,pt);
tmp = (tmp*dp[{n-i-1,pt}])%md;
ans = (ans+tmp)%md;
if(a[i]==pt+1) pt++;
}
cout << (ans+1)%md << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
588 KB |
Output is correct |
2 |
Correct |
4 ms |
588 KB |
Output is correct |
3 |
Correct |
4 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
8048 KB |
Output is correct |
2 |
Correct |
145 ms |
8160 KB |
Output is correct |
3 |
Correct |
134 ms |
8148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
772 ms |
31776 KB |
Output is correct |
2 |
Correct |
746 ms |
31548 KB |
Output is correct |
3 |
Correct |
743 ms |
31764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1094 ms |
42312 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1097 ms |
41904 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1093 ms |
43332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |