#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 1005;
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 |
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 |
1 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 |
1 ms |
292 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 |
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 |
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 |
132 ms |
8104 KB |
Output is correct |
2 |
Correct |
131 ms |
8228 KB |
Output is correct |
3 |
Correct |
135 ms |
8216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
738 ms |
31700 KB |
Output is correct |
2 |
Correct |
735 ms |
31364 KB |
Output is correct |
3 |
Correct |
738 ms |
31884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
701 ms |
32172 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |