← 返回题目列表

AtCoder · pakencamp_2024_day3_1_m

M. 两种排列

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

配点 : 100 点

問題文

(1,2,\dots,N) 的排列 给出了 P,Q 。 对于

可以通过以下步骤生成的长度 N 可以得到第 01 列 S 的数量 我们将其表示为 998244353 除的余数。 用

  • 准备 (1,2,\dots,2N) 的排列 给出了 R 。
  • 任意整数 关于 i (1 \leq i \leq N) , 当我输入R_1,R_2,\dots,R_N 中 在一行上输出 P_i 第一个最小元素是 R_i 。
  • 任意整数 关于 i (1 \leq i \leq N) , 当我输入R_{N+1},R_{N+2},\dots,R_{2N} 中 在一行上输出 Q_i 第一个最小元素是 R_{N+i} 。
  • i=1,2,\dots,N , 当我输入R_i < R_{N+i} 如果 S_i=1 、R_i > R_{N+i} 如果 S_i=0 。

制約

  • 1 \leq N \leq 200000
  • P,Q 是 您也可以写 (1,2,\dots,N) 的排列 给出了
  • 所有输入均为整数

部分点

  • N \leq 3000 的数据集,30 授予积分。
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 70 授予积分。

入力

输入是按以下格式从标准输入给出的。

N
P_1 P_2 \dots P_N
Q_1 Q_2 \dots Q_N

出力

打印答案。 来自


入力例 1

3
2 3 1
1 3 2

出力例 1

6

S=000,001,010,101,011,111(4:16 修改) 6 可以有街道。


入力例 2

5
3 4 2 1 5
3 1 2 5 4

出力例 2

11

入力例 3

10
9 2 10 3 4 8 6 7 5 1
7 8 3 4 1 6 5 2 10 9

出力例 3

43