#1950. 普通的计数题

    ID: 1950 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2398来源:qoj.ac数据:公开样例动态规划

普通的计数题

普通的计数题

题目描述

标题: 普通的计数题 - Problem - QOJ.ac

#13628. 普通的计数题

Statistics

The problem was used in the following contests:

(题目背景)是没有的。

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

  1. 在序列末端插入一个0。

  2. 在序列中删去一个子序列,并在序列末端插入一个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