102385: [AtCoder]ABC238 F - Two Exams
Description
Score : $500$ points
Problem Statement
In the Kingdom of Takahashi, $N$ citizens numbered $1$ to $N$ took an examination of competitive programming.
There were two tests, and Citizen $i$ ranked $P_i$-th in the first test and $Q_i$-th in the second test.
There were no ties in either test. That is, each of the sequences $P$ and $Q$ is a permutation of $(1, 2, ..., N)$.
Iroha, the president of the kingdom, is going to select $K$ citizens for the national team at the coming world championship of competitive programming.
The members of the national team must be selected so that the following is satisfied.
- There should not be a pair of citizens $(x, y)$ where Citizen $x$ is selected and Citizen $y$ is not selected such that $P_x > P_y$ and $Q_x > Q_y$.
- In other words, if Citizen $y$ got a rank smaller than that of Citizen $x$ in both tests, it is not allowed to select Citizen $x$ while not selecting Citizen $y$.
To begin with, Iroha wants to know the number of ways to select citizens for the national team that satisfy the condition above. Find it to help her.
Since this number can be enormous, print it modulo $998244353$.
Constraints
- All values in input are integers.
- $1 \le N \le 300$
- $1 \le K \le N$
- Each of $P$ and $Q$ is a permutation of $(1,2,...,N)$.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$ $Q_1$ $Q_2$ $\dots$ $Q_N$
Output
Print the answer as an integer.
Sample Input 1
4 2 2 4 3 1 2 1 4 3
Sample Output 1
3
- It is fine to select Citizen $1$ and Citizen $2$ for the team.
- If Citizen $1$ and Citizen $3$ are selected, Citizen $4$ ranked higher than Citizen $3$ did in both tests, so the pair $(x,y)=(3,4)$ would violate the condition in the Problem Statement.
- It is fine to select Citizen $1$ and Citizen $4$.
- If Citizen $2$ and Citizen $3$ are selected, the pair $(x,y)=(3,1)$ would violate the condition.
- It is fine to select Citizen $2$ and Citizen $4$.
- If Citizen $3$ and Citizen $4$ are selected, the pair $(x,y)=(3,1)$ would violate the condition.
The final answer is $3$.
Sample Input 2
33 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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
Sample Output 2
168558757
All $\binom{33}{16} = 1166803110$ ways of selecting $16$ from the $33$ citizens satisfy the requirement.
Therefore, we should print $1166803110$ modulo $998244353$, that is, $168558757$.
Sample Input 3
15 7 4 9 7 5 6 13 2 11 3 1 12 14 15 10 8 4 14 9 12 7 15 1 2 8 11 3 5 13 6 10
Sample Output 3
23
Input
题意翻译
在高桥王国，编号为1到N的N名国民参加了比赛程序设计的考试。 考试由2次组成，国民i在第1次考试中为第 $P_i$ 位、第2次考试中成为了第 $Q_i$ 位。 另外，无论在哪个考试中，都不会有多人排名相同。也就是说，表示名次的数列P、Q分别是（1,2、…、N）的排列。 高桥王国的总统伊吕波，根据这个考试的结果，决定从N人中选出K人作为参加竞技编程世界大会的代表。 如果国民x是代表，国民y不是代表的人，必须满足 $P_x>P_y$ 且$Q_x>Q_y$。 换句话说，尽管两次考试双方都可能国民y的排名比国民x小，但不能有国民x是代表而国民y不是代表的情况。 伊吕波想知道满足上述条件选择代表的方法的数量，请求这个数量除以998244353的余数。Output
问题描述
在Takahashi王国，编号为1到N的N位公民参加了一场编程竞赛。
共有两场测试，公民i在第一场测试中排名$P_i$，在第二场测试中排名$Q_i$。
两场测试都没有平局。即，$P$和$Q$序列都是$(1, 2, ..., N)$的排列。
Iroha，该国的总统，打算从将要参加的国际编程竞赛中选出$K$位公民组成国家队。
国家队的成员必须满足以下条件：
- 不应该存在一个公民对$(x, y)$，其中公民$x$被选中，公民$y$未被选中，且$P_x > P_y$和$Q_x > Q_y$。
- 换句话说，如果公民$y$在两场测试中都获得了比公民$x$更高的排名，那么在选中公民$x$的同时不选中公民$y$是不允许的。
首先，Iroha想知道满足上述条件的选人方式有多少种。帮助她找出答案。
由于这个数字可能非常庞大，请将它模$998244353$输出。
约束条件
- 输入中的所有值都是整数。
- $1 \le N \le 300$
- $1 \le K \le N$
- $P$和$Q$都是$(1,2,...,N)$的排列。
输入
输入通过标准输入给出，格式如下：
$N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$ $Q_1$ $Q_2$ $\dots$ $Q_N$
输出
输出一个整数作为答案。
样例输入1
4 2 2 4 3 1 2 1 4 3
样例输出1
3
- 选择公民1和公民2参加团队是可以的。
- 如果选择公民1和公民3，那么公民4在两场测试中的排名都比公民3高，因此$(x,y)=(3,4)$这对会违反问题描述中的条件。
- 选择公民1和公民4是可以的。
- 如果选择公民2和公民3，那么$(x,y)=(3,1)$这对会违反条件。
- 选择公民2和公民4是可以的。
- 如果选择公民3和公民4，那么$(x,y)=(3,1)$这对会违反条件。
最终答案是3。
样例输入2
33 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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
样例输出2
168558757
从33位公民中选出16位公民的$\binom{33}{16} = 1166803110$种方式都满足要求。
因此，我们应该输出$1166803110$模$998244353$的结果，即$168558757$。
样例输入3
15 7 4 9 7 5 6 13 2 11 3 1 12 14 15 10 8 4 14 9 12 7 15 1 2 8 11 3 5 13 6 10
样例输出3
23