PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic programming, combinatorics
PROBLEM:
For a permutation P of \{0, 1, \ldots, N-1\}, define f(P) to be the set of mex-es of all non-empty subarrays of P.
You’re given N and K. Count the number of permutations of \{0, 1, \ldots, N-1\} such that |f(P)| = K.
EXPLANATION:
For a subarray to have a MEX of x, it must contain all the values 0, 1, 2, \ldots, x-1 (in some order), and not contain the value x.
Whether there are values \gt x in the subarray does not matter at all - there can be as many or as few of them as we like.
With this mind, let’s try building a permutation P.
One way to do this, is to start with just [0] and then insert elements one by one in order.
That is, insert 1 either to the left or the right of 0, then insert 2 somewhere in the resulting order (it has three positions it can go to), then insert 3, then 4, and so on.
Whenever we insert x, there are x+1 choices for where to place it.
Every such sequence of choices will result in a different final permutation (matching the fact that there are 2\cdot 3\cdot 4\cdot\ldots\cdot N = N! possible permutations.)
Let’s now analyze how this insertion process changes the subarray mex-es of the permutation.
Suppose we’ve inserted \{0, 1, 2, \ldots, x-1\} in some order, and we now want to insert x somewhere.
Then, after inserting x,
- Any subarray that doesn’t contain x will remain unchanged, so its mex will be unchanged.
- Any subarray that does contain x corresponds to a unique subarray without x before insertion; and will have its mex changed if and only if the mex of the subarray before insertion was itself x.
This is because, if the mex of the subarray was initially \lt x, then inserting x won’t change this fact; whereas if the mex before insertion was x, then after inserting x the mex becomes x+1. - Finally, there’s the singleton subarray [x] itself, which corresponds to the empty subarray previously.
[x] has a mex of 0, which was either already present (if x \ge 2), or is new (if x = 1).
So, after inserting x, the existing mex-es smaller than x don’t change at all: they continue to exist as they are; and no new such mex-es will be created.
The only exception is 0, which is newly created when x = 1.
As for the mex of x itself: before insertion, there was exactly one subarray with mex x, and that was to take the entire array (which is a rearrangement of \{0, 1, 2, \ldots, x-1\}).
Clearly, after insertion this now transforms into the mex x+1.
However, it’s still possible to have a mex of x: in particular, this will happen if and only if the value x was inserted at either the left end or the right end; since then there will be a subarray that just has the elements \{0, 1, \ldots, x-1\} while not containing x.
In particular, observe that the number of distinct mex-es doesn’t really change much at all: if x is not inserted at an endpoint, then the number of distinct mex-es doesn’t change; and if x is inserted at an endpoint, the number of distinct mex-es increases by 1.
This allows us to use dynamic programming to count the number of permutations with exactly K distinct mex-es.
Define dp(x, y) to be the number of permutations of \{0, 1, \ldots, x-1\} that have exactly y distinct subarrays mex-es.
We then have the following transitions:
- Before inserting x-1, the permutation must’ve had either y or y-1 distinct mex-es, since as we saw inserting a new element can increase the count by at most one.
- If there were y mex-es already, inserting x-1 shouldn’t change that.
This means x-1 should not be inserted at one of the ends.
There are dp(x-1, y) choices for the permutation, and then x-2 choices for where to insert x-1 ((x-1)+1 = x choices in total, of which two are invalid). - If there were y-1 mex-es, then inserting x-1 should change that; meaning it has to be done at an endpoint.
So, there are dp(x-1, y-1) choices for the permutation, and then two choices for insertion.
Thus, we simply obtain
with the answer being dp(N, K).
x = 1 is an edge case here because of the mex 0 being always newly created.
Either handle that separately in the transitions, or just make the base case dp(2, 3) = 2 and dp(2, x) = 0 for x \ne 3, while handling N = 1 separately.
TIME COMPLEXITY:
\mathcal{O}(NK) per testcase.
CODE:
Editorialist's code (PyPy3)
mod = 10**9 + 7
for _ in range(int(input())):
n, k = map(int, input().split())
if n == 1:
print(1 if k == 1 else 0)
continue
if k < 3:
print(0)
continue
dp = [0]*(k+1)
dp[3] = 2
for i in range(2, n):
for x in reversed(range(3, k+1)):
dp[x] = (dp[x] * (i-1) + dp[x-1] * 2) % mod
print(dp[k])