Problem Statement
Nam has a permutation P = { P[1], P[2], ..., P[N] } of integers from 1 to N, inclusive.
For any such permutation we can define the following values:
- pmin(k, i) is the minimum of k consecutive elements, starting at index i
- f(k) is the maximum of pmin(k, i) over all valid choices of k consecutive elements
Formally:
- for each k and i such that 1 <= k <= N and 1 <= i <= N-k+1: pmin(k, i) = min{ P[i], P[i+1], ..., P[i+k-1] }
- f(k) = max{ pmin(k, 1), pmin(k, 2), ..., pmin(k, N-k+1) }
Nam has calculated all N values f(1), f(2), ..., f(N) and he has written them on a piece of paper. You are given these values in the int[] F of length N. For each valid i, F[i] = f(i + 1).
A few days later Nam totally forgot his permutation P. Luckily, he still kept the paper with the sequence F.
Please help him: count all permutations P that correspond to the given F and return that count modulo 998244353.
Definition
- Class:
- MaxOfMin
- Method:
- count
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int count(int[] F)
- (be sure your method is public)
Constraints
- F will have between 1 and 50 elements, inclusive.
- Each element of F will be between 1 and 50, inclusive.
Examples
{3, 1, 1}Returns: 2
Let's examine all six permutations of the set {1, 2, 3}: P = {1, 2, 3} f(1) = max(1, 2, 3) = 3 f(2) = max(1, 2) = 2 f(3) = max(1) = 1 P = {1, 3, 2} f(1) = max(1, 3, 2) = 3 f(2) = max(1, 2) = 2 f(3) = max(1) = 1 P = {2, 1, 3} f(1) = max(2, 1, 3) = 3 f(2) = max(1, 1) = 1 f(3) = max(1) = 1 P = {2, 3, 1} f(1) = max(2, 3, 1) = 3 f(2) = max(2, 1) = 2 f(3) = max(1) = 1 P = {3, 1, 2} f(1) = max(3, 1, 2) = 3 f(2) = max(1, 1) = 1 f(3) = max(1) = 1 P = {3, 2, 1} f(1) = max(3, 2, 1) = 3 f(2) = max(2, 1) = 2 f(3) = max(1) = 1 We see that there are two permutations that match the given F: the permutations {2, 1, 3} and {3, 1, 2}.{3, 1, 3}Returns: 0
As we saw above, for N = 3 there are no permutations with f(3) = 3.{5, 2, 2, 1, 1}Returns: 12
The twelve permutations that match this F are precisely the permutations in which P[2] and P[4] are 1 and 2, in either order.{6, 5, 2, 1, 1, 1}Returns: 40
{50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}Returns: 32990492
Don't forget the modulo