This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000 + 7;
const int NMAX = 10000 + 5;
int N;
int v[NMAX];
int dp[2][NMAX];
bool freq[NMAX];
int col[NMAX];
int main()
{
cin >> N;
for (int i = 1; i <= N; ++ i)
cin >> v[i];
col[0] = 0;
for (int i = 1; i <= N; ++ i) {
col[i] = col[i - 1];
if (!freq[v[i]]) {
freq[v[i]] = true;
++ col[i];
}
}
int ans = 1;
for (int i = N; i; -- i) {
if (i == N) {
for (int col = 1; col <= N; ++ col)
dp[N & 1][col] = 1;
}
else {
for (int col = 0; col <= i; ++ col)
dp[i & 1][col] = (dp[(i + 1) & 1][col + 1] + 1LL * col * dp[(i + 1) & 1][col]) % MOD;
}
ans = (ans + dp[i & 1][col[i - 1]] * (v[i] - 1LL)) % MOD;
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |