上浮记录

【题目描述】

小灰灰有一个初始为空的数组，要依次放入 $n$ 个整数 $v_1,v_2,\ldots,v_n$．数组的位置从 $1$ 开始编号．

对于位置 $p>1$，称位置 $\lfloor p/2\rfloor$ 为它的父位置；位置 $1$ 没有父位置．例如，位置 $2,3$ 的父位置都是 $1$，位置 $4,5$ 的父位置都是 $2$．

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

上图中的数字表示位置编号，不是数组中存放的数．

第 $i$ 次操作，先把 $v_i$ 放到数组末尾，即位置 $i$，再选择以下一种模式．本次刚放入的数在交换后仍会继续移动：

• 小值模式：若当前位置有父位置，且当前数严格小于父位置的数，就交换这两个数，再从父位置继续；否则停止．
• 大值模式：若当前位置有父位置，且当前数严格大于父位置的数，就交换这两个数，再从父位置继续；否则停止．

两个数相等时不交换．每次操作可以独立选择模式，不要求整个数组始终满足某一种大小顺序．

现在给出放入的数字 $v_1,v_2,\ldots,v_n$，以及希望得到的最终数组 $a_1,a_2,\ldots,a_n$．请计算有多少种模式选择序列能够得到这个最终数组，答案对 $998244353$ 取模．

只要某一次操作选择的模式不同，就视为不同序列，即使那一次没有发生交换．第一次操作也要选择模式．若无法得到给定的最终数组，答案为 $0$．

【输入描述】

第一行输入一个整数 $n$．

第二行输入 $n$ 个整数 $v_1,v_2,\ldots,v_n$，表示依次放入的数字．

第三行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示最终数组．

保证两个数组中，每个整数出现的次数相同．不保证一定存在符合要求的模式选择序列．

【输出描述】

输出一个整数，表示模式选择序列的数量对 $998244353$ 取模后的结果．

【样例 1】

【样例 1 输入】

3
2 2 3
3 2 2

【样例 1 输出】

4

【样例 1 解释】

第一次放入 $2$，两种模式都不会交换．第二次放入 $2$，它和父位置的数相等，两种模式仍都不会交换．

第三次放入 $3$，必须选择大值模式，使它与位置 $1$ 的 $2$ 交换，得到数组 $[3,2,2]$．前两次分别有两种选择，因此共有 $4$ 种序列．

【样例 2】

【样例 2 输入】

3
1 2 3
2 3 1

【样例 2 输出】

0

【样例 2 解释】

前两次操作后，数组只能是 $[1,2]$ 或 $[2,1]$．第三次放入的 $3$ 只可能停在位置 $3$，或与位置 $1$ 的数交换，不能到达位置 $2$．

【数据规模与约定】

对于所有数据，$1\le n\le2\times10^5$，$1\le v_i,a_i\le10^9$．

本题采用捆绑测试．只有通过一个子任务的全部测试点，才能获得该子任务的分数．

子任务编号	分数	附加限制
1	20	$n\le18$
2	10	$v_1=v_2=\cdots=v_n$
3		$v_1<v_2<\cdots<v_n$
4	25	$v_i$ 两两不同
5	35	无

【下发样例】

• Data/sample1.in 与 Data/sample1.ans：样例 1．
• Data/sample2.in 与 Data/sample2.ans：样例 2．
• Data/sample3.in 与 Data/sample3.ans：满足子任务 1 的限制．
• Data/sample4.in 与 Data/sample4.ans：满足子任务 2 的限制．
• Data/sample5.in 与 Data/sample5.ans：满足子任务 3 的限制．
• Data/sample6.in 与 Data/sample6.ans：满足子任务 4 的限制．
• Data/sample7.in 与 Data/sample7.ans：该样例无特殊限制．
• Data/sample8.in 与 Data/sample8.ans：该样例无特殊限制．
• Data/sample9.in 与 Data/sample9.ans：该样例无特殊限制．
• Data/sample10.in 与 Data/sample10.ans：该样例无特殊限制．

点击下载本题选手目录