Three Minimums
Contest: Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)
Difficulty rating: 3500
Tags: combinatorics, constructive algorithms, divide and conquer, dp, fft, math

Given a list of distinct values, we denote with first minimum, second minimum, and third minimum the three smallest values (in increasing order).

A permutation $$$p_1, p_2, \dots, p_n$$$ is good if the following statement holds for all pairs $$$(l,r)$$$ with $$$1\le l < l+2 \le r\le n$$$.

- If $$$\{p_l, p_r\}$$$ are (not necessarily in this order) the first and second minimum of $$$p_l, p_{l+1}, \dots, p_r$$$ then the third minimum of $$$p_l, p_{l+1},\dots, p_r$$$ is either $$$p_{l+1}$$$ or $$$p_{r-1}$$$.

You are given an integer $$$n$$$ and a string $$$s$$$ of length $$$m$$$ consisting of characters "<" and ">".

Count the number of good permutations $$$p_1, p_2,\dots, p_n$$$ such that, for all $$$1\le i\le m$$$,

- $$$p_i < p_{i+1}$$$ if $$$s_i =$$$ "<";
- $$$p_i > p_{i+1}$$$ if $$$s_i =$$$ ">".

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \leq m \leq \min(100, n-1)$$$).

The second line contains a string $$$s$$$ of length $$$m$$$, consisting of characters "<" and ">".

Output format:
Print a single integer: the number of good permutations satisfying the constraints described in the statement, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 8.0 s
Memory limit: 1024.0 MB

Note:
In the first test, there are $$$5$$$ good permutations satisfying the constraints given by the string $$$s$$$: $$$[4, 3, 2, 1, 5]$$$, $$$[5, 3, 2, 1, 4]$$$, $$$[5, 4, 2, 1, 3]$$$, $$$[5, 4, 3, 1, 2]$$$, $$$[5, 4, 3, 2, 1]$$$. Each of them

- is good;
- satisfies $$$p_1 > p_2$$$;
- satisfies $$$p_2 > p_3$$$;
- satisfies $$$p_3 > p_4$$$.

In the second test, there are $$$60$$$ permutations such that $$$p_1 < p_2$$$. Only $$$56$$$ of them are good: the permutations $$$[1, 4, 3, 5, 2]$$$, $$$[1, 5, 3, 4, 2]$$$, $$$[2, 4, 3, 5, 1]$$$, $$$[2, 5, 3, 4, 1]$$$ are not good because the required condition doesn't hold for $$$(l, r)$$$ = $$$(1, 5)$$$. For example, for the permutation $$$[2, 4, 3, 5, 1]$$$,

- the first minimum and the second minimum are $$$p_5$$$ and $$$p_1$$$, respectively (so they are $$$\{p_l, p_r\}$$$ up to reordering);
- the third minimum is $$$p_3$$$ (neither $$$p_{l+1}$$$ nor $$$p_{r-1}$$$).

In the third test, there are $$$23$$$ good permutations satisfying the constraints given by the string $$$s$$$: $$$[1, 2, 4, 3, 6, 5]$$$, $$$[1, 2, 5, 3, 6, 4]$$$, $$$[1, 2, 6, 3, 5, 4]$$$, $$$[1, 3, 4, 2, 6, 5]$$$, $$$[1, 3, 5, 2, 6, 4]$$$, $$$[1, 3, 6, 2, 5, 4]$$$, $$$[1, 4, 5, 2, 6, 3]$$$, $$$[1, 4, 6, 2, 5, 3]$$$, $$$[1, 5, 6, 2, 4, 3]$$$, $$$[2, 3, 4, 1, 6, 5]$$$, $$$[2, 3, 5, 1, 6, 4]$$$, $$$[2, 3, 6, 1, 5, 4]$$$, $$$[2, 4, 5, 1, 6, 3]$$$, $$$[2, 4, 6, 1, 5, 3]$$$, $$$[2, 5, 6, 1, 4, 3]$$$, $$$[3, 4, 5, 1, 6, 2]$$$, $$$[3, 4, 5, 2, 6, 1]$$$, $$$[3, 4, 6, 1, 5, 2]$$$, $$$[3, 4, 6, 2, 5, 1]$$$, $$$[3, 5, 6, 1, 4, 2]$$$, $$$[3, 5, 6, 2, 4, 1]$$$, $$$[4, 5, 6, 1, 3, 2]$$$, $$$[4, 5, 6, 2, 3, 1]$$$.

Example input:
5 3
>>>

Example output:
5

Example input:
5 1
<

Example output:
56

Editorial:
First of all, let us state the following lemma (which is sufficient to solve the problem in O(n2) if one ignores the constraints given by the string s
). We omit the proof as it is rather easy compared to the difficulty of the problem as a whole.
Lemma: The following statements hold for a permutation p1,p2,…,pn
.
p
is good if and only if p[1:i] and p[i:n] are good, where pi=1 . If p1=1 , then p is good if and only if p[1:i] and p[i:n] are good, where pi=2 . If p1=1 and pn=2, then p is good if and only if it is bitonic, i.e., p1<p2<p3<⋯<pi>pi+1>⋯pn−1>pn, where pi=n
.
Given 1≤l<r≤n , we say that a permutation q1,q2,…,qr−l+1 of 1,2,…,r−l+1 is [l,r]-consistent if for any l≤i≤min(r,m−1)
:
qi−l+1<qi−l+2
if si=< ; qi−l+1>qi−l+2 if si=>
.
Informally speaking, a permutation is [l,r] -consistent if it satisfies the constraints given by s when it is written in the positions [l,r]
.
For 1≤l<r≤n , let a∗∗(l,r), a1∗(l,r), a∗1(l,r), a12(l,r), a21(l,r) be the the number of good permutations which are [l,r]
-consistent and, respectively,
No additional conditions; Start with 1
; End with 1 ; Start with 1 and end with 2 ; Start with 2 and end with 1
.
For 1≤i<n and c∈<,>, let q(i,c):=[i>m or si=c]. Informally speaking, q(i,<) is 1 if and only if it can be pi<pi+1 and q(i,>) is 1 if and only if it can be pi>pi+1
.
Thanks to the Lemma, one has the following relations:
a∗∗(l,r)=∑ri=la∗1(l,i)a1∗(i,r)(r−li−l)
. a1∗(l,l)=1 . For l<r, a1∗(l,r)=∑ri=l+1a12(l,i)a1∗(i,r)(r−l−1i−l−1) . Analogous formula for a∗1 . a12(l,l)=0 and a12(l,l+1)=q(l,<) and a12(l,l+2)=q(l,<)⋅q(l+1,>). For l<l+1<r, a12(l,r)=q(l,<)a21(l+1,r)+q(r−1,>)a12(l,r−1) . Analogous formula for a21
.
The problem asks to compute a∗∗(1,n) . Thanks to the formulas stated above, it is straightforward to implement an O(n2) solution. Now we will tackle the hard task of optimizing it to O(nm+nlog(n))
.
In order to compute a∗∗(1,n) , we will compute a∗1(1,k) and a1∗(k,n) for all 1≤k≤n
.
We have the recurrence relation (for k≥2
) a∗1(1,k)=∑ki=1a∗1(1,i)a21(i,k)(k−2i−1)(1)
Setting xk−1:=a∗1(1,k)/(k−1)! , (1) is equivalent to (for k≥1, and also for k=0
!) k⋅xk=∑k−1i=0xia21(i+1,k+1)(k−1−i)!.(2)
This looks very similar to an identify between generating functions (a derivative on the left, a product on the right); but for the fact that a21
depends on two parameters. To overcome this issue let us proceed as follows.
Notice that, if we set b to any of the functions a∗∗, a∗1, a1∗, a12, a21, it holds b(l,r)=b(l+1,r+1) whenever l>m. Hence, let us define b∗∗(k)=a∗∗(n+1,n+k) and analogously b1∗(k), b∗1(k), b12(k), b21(k)
.
With these new definitions, (2) becomes (for k≥0
) k⋅xk=∑k−1i=0xib21((k−1−i)+2)(k−1−i)!+∑min(k−1,m−1)i=0xia21(i+1,k+1)−b21(k+1−i)(k−1−i)!.(3)
Let ui:=b21(i+2)i! and vk−1:=∑min(k−1,m−1)i=0xib21(k+1−i)−a21(i+1,k+1)(k−1−i)!
. So, (3) simplifies to k⋅xk=vk−1+∑k−1i=0xiuk−1−i.(4)
We precompute in O(nm) the values of a12(l,r) and a21(l,r) for 1≤l≤m, l<r≤n. We can also precompute in O(n) the values of b12(k),b21(k) for 1≤k≤n. In O(m2) we compute also xi for all 0≤i≤m−1. Thus, in O(nm) we can compute, for all 0≤k<n, the values uk
.
It is now time to start working with generating functions. Let X(t):=∑k≥0xktk , U(t):=∑k≥0uktk, V(t):=∑k≥0vktk. We know U(t) and V(t) (at least the first n coefficients) and we want to compute X(t). Since x0=1, we know X(0)=1. Moreover (4) is equivalent to the ordinary differential equation X′=V+U⋅X
. This ODE is standard and its (unique) solution is given by X=exp(∫U)(1+∫Vexp(−∫U)).
Since the product of generating functions and the exponential of a generating function can be computed in O(nlog(n)) , we are able to obtain the values of xk for all 0≤k<n and thus the values of a∗1(1,k)
.
Now, let us see how to compute a1∗(k,n) . Since a1∗(k,n)=b1∗(n−k+1) for all m<k≤n, let us first compute b1∗(k) for all 1≤k≤n. By repeating verbatim the reasoning above, we get that the generating function Y(t):=∑k≥0yktk, where yk−1:=b1∗(k)/(k−1)!, is given by (V=0 in this case) Y=exp(∫U). So, it remains only to compute a1∗(k,n) for 1≤k≤m. This can be done naïvely in O(nm)
.
The overall complexity is O(nm+nlog(n)) .