F - Two Exams

Contest Duration: 2022-02-05(Sat) 12:00 - 2022-02-05(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Two Exams Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

高橋王国にて、 $1$ から $N$ までの番号のついた $N$ 人の国民が競技プログラミングの試験に参加しました。
試験は $2$ 回からなり、人 $i$ は $1$ 回目の試験で $P_i$ 位、 $2$ 回目の試験で $Q_i$ 位となりました。
なお、どちらの試験においても、複数人が同じ順位になることはありませんでした。すなわち、順位を表す数列 $P,Q$ はそれぞれ $(1,2,...,N)$ の順列です。

高橋王国の大統領であるいろはちゃんは、この試験の結果に基づいて、 $N$ 人の中から競技プログラミングの世界大会に出場する $K$ 人の代表を決めることになりました。
代表を決めるにあたって、以下が成立していなければなりません。

人 $x$ が代表であり、人 $y$ が代表でないような人の組 $(x,y)$ であって、 $P_x > P_y$ かつ $Q_x > Q_y$ であるようなものが存在してはならない。
- 言い換えると、 $2$ 回の試験の双方で人 $y$ が人 $x$ よりも小さい順位を取っているにも拘らず、人 $x$ が代表で人 $y$ が代表でないということがあってはならない。

いろはちゃんは、ひとまず上記の条件を満たす代表の選び方の数を知りたいので、この数を求めてください。
ただし、この数は非常に大きくなる場合もあるので、 $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$

出力

答えを整数として出力せよ。

入力例 1Copy

Copy

4 2
2 4 3 1
2 1 4 3

出力例 1Copy

Copy

人 $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$ 通りです。

入力例 2Copy

Copy

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

出力例 2Copy

Copy

168558757

$33$ 人から $16$ 人を選ぶ $\binom{33}{16} = 1166803110$ 通りの全てにおいて、問題文中の条件を満たします。
よって、 $1166803110$ を $998244353$ で割った余りである $168558757$ を出力することとなります。

入力例 3Copy

Copy

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

出力例 3Copy

Copy

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 1Copy

Copy

4 2
2 4 3 1
2 1 4 3

Sample Output 1Copy

Copy

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 2Copy

Copy

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 2Copy

Copy

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 3Copy

Copy

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 3Copy

Copy