Tyler and Strings

题意翻译

给定长为 $n$ 的序列 $s$ 和长为 $m$ 的序列 $t$，问将 $s$ 重新排列后能得到多少个不同的字典序小于 $t$ 的序列。 两个序列 $a,b$ 被视为不同当且仅当至少存在一个 $i$ 使得 $a_i\neq b_i$。

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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 $ .

输入输出样例

输入样例 #1

3 4
1 2 2
2 1 2 1

输出样例 #1

2

输入样例 #2

4 4
1 2 3 4
4 3 2 1

输出样例 #2

23

输入样例 #3

4 3
1 1 1 2
1 1 2

输出样例 #3

1

说明

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.