#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>,
// rb_tree_tag, tree_order_statistics_node_update>;
const int maxn = 10001;
#define mp make_pair
#define pb push_back
#define f first
#define s second
const int mod = 1000007;
typedef pair<int, int> pii;
int n;
int seq[maxn];
ll dp[2][maxn]; // we're going to sliding window on the first dimension
/*
We're looking at sequences of the integers 1..k, where the first occurrence of 1..k are in precisely that order
- interesting note: this means that all sequences should start with 1
Want to find how many of these sequences appear lexicographically before our current sequence
number of seuqences of each length
1: 1
2: 2
3: 5
4: 15
1 2 2
- Everything with 1 1 is before: there are 2 options (that's easy to count)
- Everything with 1 2 1 is before: only 1 option
- this should be 4
Observation: the first n numbers in a length n+1 sequence also form a valid sequence (maybe we'll just call them sequences from now on)
- from a length n sequence where the numbers 1..k are used, you have k+1 options for the next thing to append to it
1 2 3 2
- everything that starts with a sequence that is before 1 2 3 is before it
- this is still problematic though because of the fact that the number of ways to make a sequence of length 4 depends on the numbers used
What if we have a function S(n, k) that tells us the number of sequences of size n that use 1..k
S(n+1, k) = S(n, k-1) + kS(n, k)
This is stirling numbers of the second kind
So the number of sequences is the Bell numbers
Size n = number of ways to partition a set of size n, the largest element we use should somehow correlate to the number of subsets
There should be one subset per each number
Wait this bijection is literally what the question is asking
So I guess back to the examples: 1 2 3 2
The problem is that we don't just need the number of 3-sequences below 1 2 3, we need for each sequence the highest k value that it uses, which seems a lot harder to get
Is it easy to count everything that starts with 1 1?
- yes because there should just be 5 (the number of length 3 sequences)
What about 1 2 1: this is fine for now because there's only one more option, but what about when we need something of like length 5
- Ok this fowards strategy seems quite bad
This still feels like a dp problem
Let T(m, k) be the number of sequences of size m using 1..k that are strictly lower in lexicographic order than the first m elements of our sequence
Answer would be sum of the T(n, 1..n)
There are n^2 states = 10^8 which might run in time
The transition
T(i+1, j) = (number of sequences that perfectly match first i and have lower i+1th position) + T(i, j-1) + jT(i, j)
This seems O(1) enough
Figuring out the first part is just a matter of preprocessing which numbers are used at each point in our given sequence
Sliding window so that we have enough memory
*/
void setupIO(string s)
{
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
int main()
{
//setupIO("calvinball");
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i=0; i<n; i++)
{
cin >> seq[i];
}
int largestnum = 1;
for (int i=1; i<n; i++)
{
for (int j=1; j<=i+1; j++)
{
dp[i%2][j] = (dp[(i-1)%2][j-1] + j*dp[(i-1)%2][j])%mod;
if (largestnum == j)
{
dp[i%2][j] = (dp[i%2][j]+seq[i]-1)%mod;
//because seq[i] is at most largestnum+1, so the largest number used in any sequence that's the first i-1 terms + something lower than seq[i] is largestnum
}
}
largestnum = max(largestnum, seq[i]);
}
ll ans = 1;
for (int i=1; i<=n; i++)
{
ans = (ans + dp[(n-1)%2][i])%mod;
}
cout << ans << endl;
}
Compilation message
teams.cpp: In function 'void setupIO(std::string)':
teams.cpp:78:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:79:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
| 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 |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 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 |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
412 KB |
Output is correct |
| 2 |
Correct |
31 ms |
332 KB |
Output is correct |
| 3 |
Correct |
31 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
536 KB |
Output is correct |
| 2 |
Correct |
125 ms |
472 KB |
Output is correct |
| 3 |
Correct |
121 ms |
520 KB |
Output is correct |
