#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 10001;
const ll md = 1e6+7;
int n, a[MAXN], pt = 0;
int ans = 0;
map <pair<int,int>,int> dp;
inline int mdd(ll x){
return (x>=md?x%md:x);
}
void get(int sz, int t){
if(dp[{sz,t}]) return;
if(sz==0){
dp[{sz,t}] = 1;
return;
}
get(sz-1,t); get(sz-1,t+1);
dp[{sz,t}] = mdd((ll)t*(ll)dp[{sz-1,t}])+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 = mdd(tmp*(ll)dp[{n-i-1,pt}]);
ans = ((ll)ans+tmp>=md?(ll)ans+tmp-md:(ll)ans+tmp);
if(a[i]==pt+1) pt++;
}
cout << (ans+1)%md << '\n';
return 0;
}
# |
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 |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 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 |
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 |
# |
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 |
564 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 |
134 ms |
8084 KB |
Output is correct |
2 |
Correct |
137 ms |
8144 KB |
Output is correct |
3 |
Correct |
137 ms |
8220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
759 ms |
31588 KB |
Output is correct |
2 |
Correct |
720 ms |
31420 KB |
Output is correct |
3 |
Correct |
757 ms |
31720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1086 ms |
43304 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1096 ms |
42564 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1097 ms |
43164 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |