#1950. 普通的计数题
普通的计数题
普通的计数题
题目描述
标题: 普通的计数题 - Problem - QOJ.ac
#13628. 普通的计数题
The problem was used in the following contests:
(题目背景)是没有的。
你有一个01序列,初始时序列为空。你可以对序列进行两种操作:
-
在序列末端插入一个0。
-
在序列中删去一个子序列,并在序列末端插入一个1。这里对子序列的选取有一定限制,设子序列中包含x个0,y个1,则你选取的子序列必须满足:
- 子序列不可为空,即x+y>0
- 当y>0时,x∈A,这里A为给定集合
- 当y=0时,x∈B,这里B为给定集合
现在,你需要对序列执行n次操作。请你求出在所有不同的操作方案中,最终序列长度为1的方案有多少种。两种操作方案被视为不同,当且仅当某一次操作的种类不同,或某个第二类操作中选取的子序列不同(子序列不同指的是位置不同,与值无关)。
答案对998244353取模。
输入格式
输入第一行包含三个整数n,|A|,|B|,表示操作的次数,集合A的大小,集合B的大小。
输入第二行包含|A|个整数a1,a2,⋯,a|A|,描述集合A的各个元素。
输入第三行包含|B|个整数b1,b2,⋯,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
限制与约定
本题使用捆绑测试。
子任务分值限制 15n≤10 220n≤2000 35|A|=|B|=n 430A=B 540无特殊限制
对于所有数据,1≤n≤120000,0≤ai,bi<n,ai互不相同,bi互不相同。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 1 1
1
1
3
样例 2
10 10 10
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
362880