From constructive version, we can get criteria for pair of sequences (P, S) being viable:
-
P_1 = 1, P_{i-1} \le P_i \le P_{i-1}+1 for all i>1.
-
S_N = 1, S_{i+1} \le S_i \le S_{i+1}+1 for all i<N.
-
P_N = S_1. We will denote this value by L (which is LIS(A)).
-
P_i + S_i \ge L+1 for all 1 \le i \le N.
-
If P_i = P_{i-1} + 1 and S_i = S_{i+1} + 1, then P_i + S_i = L + 1 must hold.
Let’s create sequence D_i = L - S_i. Then, our conditions are equivalent to:
-
D_1 = 0 \le D_2 \ldots \le D_n = L - 1
-
D_{i + 1} \le D_i + 1
-
D_i \le P_i - 1
-
if D_{i + 1} = D_i + 1 then either P_i = P_{i - 1} or D_i = P_i - 1.
If we will mark points (i, D_i) on plane, it will correspond to pathes from (1, 0) to (n, L - 1) which never go above some fixed path and have some constraints on going up.
To solve this problem we will use D&C approach.
We will run recursive function, which will be given limits on heights a_1, a_2, \ldots a_n and coefficients for starting points (1, 0), (2, 1), \ldots (n, 0) will return number of pathes from starting points to (n, 0), (n, 1), \ldots (n, a_n), where we take coefficients into account(so if there are two pathes from (1, 0) to (n, 1) and сoefficient for (1, 0) is equal to 3 we should add 6 for the point (n, 1)).
For the original problem we will need to set a_i = P_i - 1, coefficient 1 for (1, 0) and 0 for all others.
Let’s briefly describe how we can reduce our problem to smaller ones. Let’s choose mid = n / 2 (cases of n \le 2 should be treated separately).
Firstly we will solve problem for a_1, \ldots a_{mid} with the same coefficients for (1, 0) \ldots (mid, 0). After this, we can forget about this mid points. Then, we have rectangle made of lines x = mid, x = n, y = 0, y = a_mid and we need to consider pathes from the left and bottom side of this rectangle. It’s see to see that each of those pathes will either intersect up or right side of this rectangle. Our plan is for each point on up and right side to calculate how many pathes will pass through it, and call recursive function for upper part with new limits a_{mid} - a_{mid}, a_{mid + 1} - a_{mid}, \ldots a_n - a_{mid} and coefficients calculated for upper part of rectangle. After that we should also add answers calculated for the right part.
So the only question left is how to calculate number of pathes with coefficients, going from left/bottom of rectangle to up/right. We can do it separately for each side, using FFT.
All 4 parts are rather similar(though polynomials will be different). I will describe approach for left/right.
If we start from (mid, x) and want to go (n, y), number of such pathes is K\choose{y - x} where K is number of allowed increases by one on the segment [mid, n].
Then, we can create polynomials, with x^i K\choose{i} and x^i \cdot coef_i where coef_i denotes resulting coefficient for (mid, i). Then, if we multiply them, coefficient of x^j will be equal to number of pathes to (n, j).
Overall, we will have O(nlog(n)) over each layer of call of our function and O(nlog^2(n)) in total.