AT_abc238_f [ABC238F] Two Exams

题目描述

在高桥王国，有 $N$ 位编号为 $1$ 到 $N$ 的国民参加了竞赛编程考试。
考试分为两轮，第 $i$ 个人在第一轮考试中获得了第 $P_i$ 名，在第二轮考试中获得了第 $Q_i$ 名。
此外，在每一轮考试中，没有多人获得相同的名次。也就是说，表示名次的数列 $P,Q$ 都是 $1$ 到 $N$ 的一个排列。

高桥王国的总统いろは酱需要根据这次考试的结果，从 $N$ 个人中选出 $K$ 人作为代表，参加竞赛编程的世界大会。
在选拔代表时，必须满足以下条件：

• 不存在一对 $(x, y)$，其中 $x$ 是代表，$y$ 不是代表，且 $P_x > P_y$ 且 $Q_x > Q_y$。
  • 换句话说，不能出现这样一种情况：在两轮考试中，$y$ 的名次都比 $x$ 更靠前，但 $x$ 被选为代表而 $y$ 没有被选为代表。

いろは酱想知道，满足上述条件的代表选法有多少种。
由于答案可能非常大，请输出答案对 $998244353$ 取模后的结果。

输入格式

输入按以下格式从标准输入读入。

$N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$ $Q_1$ $Q_2$ $\dots$ $Q_N$

输出格式

请输出一个整数，表示满足条件的代表选法数量。

输入输出样例 #1

输入 #1

4 2
2 4 3 1
2 1 4 3

输出 #1

3

输入输出样例 #2

输入 #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

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 300$
• $1 \leq K \leq N$
• $P,Q$ 都是 $1$ 到 $N$ 的一个排列。

样例解释 1

• 选择第 $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$ 个人的方案数为 $\binom{33}{16} = 1166803110$，所有方案都满足题目中的条件。因此，输出 $1166803110$ 对 $998244353$ 取模后的结果 $168558757$。

由 ChatGPT 4.1 翻译