UOJ Logo Universal Online Judge

UOJ

#428. 【集训队作业2018】普通的计数题

统计

(题目背景)是没有的。

你有一个$01$序列,初始时序列为空。你可以对序列进行两种操作:

  1. 在序列末端插入一个$0$。
  2. 在序列中删去一个子序列,并在序列末端插入一个$1$。这里对子序列的选取有一定限制,设子序列中包含$x$个$0$,$y$个$1$,则你选取的子序列必须满足:
    • 子序列不可为空,即$x+y>0$
    • 当$y>0$时,$x\in A$,这里$A$为给定集合
    • 当$y=0$时,$x\in B$,这里$B$为给定集合

现在,你需要对序列执行$n$次操作。请你求出在所有不同的操作方案中,最终序列长度为$1$的方案有多少种。两种操作方案被视为不同,当且仅当某一次操作的种类不同,或某个第二类操作中选取的子序列不同(子序列不同指的是位置不同,与值无关)。

答案对$998244353$取模。

输入格式

输入第一行包含三个整数$n,|A|,|B|$,表示操作的次数,集合$A$的大小,集合$B$的大小。

输入第二行包含$|A|$个整数$a_1,a_2,\cdots,a_{|A|}$,描述集合$A$的各个元素。

输入第三行包含$|B|$个整数$b_1,b_2,\cdots,b_{|B|}$,描述集合$B$的各个元素。

输出格式

输出一个整数,表示答案。

样例一

input

4 1 1
1
1

output

3

样例二

input

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

output

362880

限制与约定

本题使用捆绑测试。

子任务分值限制
$1$$5$$n\leq 10$
$2$$20$$n\leq 2000$
$3$$5$$|A|=|B|=n$
$4$$30$$A=B$
$5$$40$无特殊限制

对于所有数据,$1\leq n\leq 120000,0\leq a_i,b_i< n$,$a_i$互不相同,$b_i$互不相同。

时间限制:$2\texttt{s}$

内存限制:$512\texttt{MB}$

下载

样例数据下载