Tyler and Strings
Contest: Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 1900
Tags: combinatorics, data structures, implementation

While looking at the kitchen fridge, the little boy Tyler noticed magnets with symbols, that can be aligned into a string $$$s$$$.

Tyler likes strings, and especially those that are lexicographically smaller than another string, $$$t$$$. After playing with magnets on the fridge, he is wondering, how many distinct strings can be composed out of letters of string $$$s$$$ by rearranging them, so that the resulting string is lexicographically smaller than the string $$$t$$$? Tyler is too young, so he can't answer this question. The alphabet Tyler uses is very large, so for your convenience he has already replaced the same letters in $$$s$$$ and $$$t$$$ to the same integers, keeping that different letters have been replaced to different integers.

We call a string $$$x$$$ lexicographically smaller than a string $$$y$$$ if one of the followings conditions is fulfilled:

- There exists such position of symbol $$$m$$$ that is presented in both strings, so that before $$$m$$$-th symbol the strings are equal, and the $$$m$$$-th symbol of string $$$x$$$ is smaller than $$$m$$$-th symbol of string $$$y$$$.
- String $$$x$$$ is the prefix of string $$$y$$$ and $$$x \neq y$$$.

Because the answer can be too large, print it modulo $$$998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 200\,000$$$) — the lengths of strings $$$s$$$ and $$$t$$$ respectively.

The second line contains $$$n$$$ integers $$$s_1, s_2, s_3, \ldots, s_n$$$ ($$$1 \le s_i \le 200\,000$$$) — letters of the string $$$s$$$.

The third line contains $$$m$$$ integers $$$t_1, t_2, t_3, \ldots, t_m$$$ ($$$1 \le t_i \le 200\,000$$$) — letters of the string $$$t$$$.

Output format:
Print a single number — the number of strings lexicographically smaller than $$$t$$$ that can be obtained by rearranging the letters in $$$s$$$, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the strings we are interested in are $$$[1\, 2\, 2]$$$ and $$$[2\, 1\, 2]$$$. The string $$$[2\, 2\, 1]$$$ is lexicographically larger than the string $$$[2\, 1\, 2\, 1]$$$, so we don't count it.

In the second example, all strings count except $$$[4\, 3\, 2\, 1]$$$, so the answer is $$$4! - 1 = 23$$$.

In the third example, only the string $$$[1\, 1\, 1\, 2]$$$ counts.

Example input:
3 4
1 2 2
2 1 2 1

Example output:
2

Example input:
4 4
1 2 3 4
4 3 2 1

Example output:
23

Editorial:
Let $$$K$$$ be the size of the alphabet, that is, the number of the maximum letter that occurs in it.
First, let's calculate how many different strings can be composed if we have $$$c_1$$$ letters of the $$$1$$$th type, $$$c_2$$$ letters of the $$$2$$$th type, $$$\ldots$$$, $$$c_K$$$ letters of the $$$K$$$ type. This is the school formula:
$$$P(c_1, c_2, \ldots, c_K) = \frac{(c_1 + c_2 + \ldots + c_K)!}{c_1! \cdot c_2! \cdot \ldots \cdot c_K!} $$$
to quickly calculate it for different $$$c_1, c_2, \ldots, c_k$$$ pre-calculate all factorials and their reciprocals modulo $$$C = 998244353$$$ in O($$$n \cdot \log{C}$$$)
In order for the string $$$x$$$ to be less than the string t, they must have the same prefix. Let's iterate over the length of this matching prefix from $$$0$$$ to $$$\min(n, m)$$$. If strings $$$x$$$ and $$$t$$$ have the same first $$$i$$$ characters, then we know exactly how many letters we have left. To support this, let's create an array cnt, at the $$$i$$$-th position of which there will be the number of remaining letters of type $$$i$$$.
Let's iterate over the letter that will appear immediately after the matching prefix. For the resulting string to be less than $$$t$$$, this letter must be strictly less than the corresponding letter in $$$t$$$, and all subsequent letters can be arranged in any order. Let's calculate the number of rows $$$x$$$ considered in this way according to the formula above.
The only case where the resulting string $$$x$$$ can be lexicographically less than $$$t$$$, which we will not count, is when it is a prefix of the string $$$t$$$, but has a shorter length. We will separately check whether we can get such a string, and if so, add 1 to the answer.
Since at each of at most $$$\min(n, m)$$$ steps we need to go through at most $$$K$$$ options for the next letter, and we calculate each option in O($$$K$$$) - we get the asymptotics O($$$\min (n, m) \cdot K^2 + n \cdot \log{C}$$$)
To speed up the resulting solution, let's create an array $$$add$$$, in the $$$i$$$-th cell of which we store how many ways it will be possible to arrange the remaining letters if the letter $$$i$$$ is put in the current position. In fact $$$add_i = \frac{(cnt_1 + cnt_2 + \ldots + cnt_K - 1)!}{cnt_1! \cdot cnt_2! \cdot \ldots \cdot (cnt_i - 1)! \cdot \ldots \cdot cnt_K!}$$$
If we learn how to maintain this array, then at each step we only need to take the sum of the elements at some of its prefix. Let's see how it changes if the next letter in the string $$$t$$$ is $$$i$$$, i.e. $$$cnt_i$$$ should decrease by 1.
For all cells $$$j \neq i$$$ $$$add_j$$$ is replaced by $$$add_j \cdot \frac{cnt_i}{cnt_1 + cnt_2 + \ldots + cnt_K - 1}$$$. To apply modifications to the entire array, let's create a separate variable $$$modify$$$, by which we need to multiply the value in the cell to get the value that should be there.
For cell $$$i$$$, $$$add_i$$$ will be replaced by $$$add_i \cdot \frac{cnt_i - 1}{cnt_1 + cnt_2 + \ldots + cnt_K - 1}$$$. And taking into account the fact that we applied a modifier to all cells, it is enough to multiply the value of $$$add_i$$$ by $$$\frac{cnt_i - 1}{cnt_i}$$$
With this optimization, we now spend only O(K) actions at each step to calculate the prefix sum, and O($$$\log(C)$$$) to calculate what to multiply the array cells by. We get the asymptotics O($$$\min(n, m) \cdot (K + \log(C))$$$) To get rid of $$$K$$$ asymptotically, note that the only thing we want to do with the $$$add$$$ array is take the sum at the prefix and change the value at the point. This can be done in O($$$log(K)$$$ using the Fenwick Tree or the Segment Tree. Applying them, we get the final asymptotic O($$$\min(n, m) \cdot (\log(K) + \log(C)) $$$).
In fact, $$$\log(C)$$$ in the asymptotics can be eliminated by precalculating modulo reciprocals for all numbers from $$$1$$$ to $$$n$$$ faster than O($$$n \cdot \log(C)$$$), but in this task was not required.