← 返回题目列表

AtCoder · abc238_f

I. 两次考试

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

在高桥王国, N 编号为公民 1 to N 参加了竞争性编程考试。
有两次测试,西铁城 i 排名 P_i- 第一个测试中的第一个和 Q_i- 第二次测试中的第一个。
两项测试均没有平局。也就是说,每个序列 P 和 Q 是一个排列 (1, 2, ..., N).

王国总统伊吕波即将选择 K 公民代表国家队参加即将举行的世界竞技编程锦标赛。
国家队成员的选择必须满足以下条件。

  • 不应该有一对公民 (x, y) 其中西铁城 选择 x 并且西铁城 未选择 y 使得 P_x > P_y 和 Q_x > Q_y.
    • 换句话说,如果公民 y 的排名低于公民 x 在两次测试中都不允许选择Citizen x 未选择 Citizen 时 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

输出

将答案打印为整数。


示例输入 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

全部 \binom{33}{16} = 1166803110 选择方式 16 来自 33 公民满足要求。
因此,我们应该打印 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