AT_abc238_f.[ABC238F] Two Exams

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

不存在一对 $(x, y)$ $(x, y)$ ，其中 $x$ $x$ 是代表， $y$ $y$ 不是代表，且 $P_x > P_y$ $P_{x} > P_{y}$ 且 $Q_x > Q_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
```
4 2
2 4 3 1
2 1 4 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

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

说明/提示

限制条件

所有输入均为整数。
$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页