#P13681. [ARC127E] Priority Queue

    ID: 12883 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-栈交换论证补集转化计数 DP滚动数组倒序更新避免重复使用

[ARC127E] Priority Queue

题目描述

给定一个长度为 A+BA+B 的整数序列 (X1,X2,⋯ ,XA+B)(X_1,X_2,\cdots,X_{A+B})。XX 恰好包含 AA 个 11 和 BB 个 22。

すぬけくん有一个集合 ss,最开始 ss 为空。他将进行 A+BA+B 次操作,第 ii 次操作如下:

  • 当 Xi=1X_i=1 时:选择一个满足 1≤v≤A1\leq v\leq A 的整数 vv,并将其加入 ss。但之前已经选择过的整数不能再次选择为 vv。
  • 当 Xi=2X_i=2 时:从 ss 中删除当前的最大元素。保证在进行该操作前,ss 不为空。

请问最终可能得到多少种不同的 ss 集合?请将答案对 998244353998244353 取模后输出。

输入格式

输入通过标准输入给出,格式如下:

AA BB X1X_1 X2X_2 ⋯\cdots XA+BX_{A+B}

输出格式

输出一个整数,表示最终可能得到的不同 ss 集合的数量,对 998244353998244353 取模。

输入输出样例 #1

输入 #1

3 1
1 1 2 1

输出 #1

2

输入输出样例 #2

输入 #2

20 6
1 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 1 1 1 2 1 1 1 1 1

输出 #2

5507

说明/提示

限制条件

  • 1≤A≤50001\leq A\leq 5000
  • 0≤B≤A−10\leq B\leq A-1
  • 1≤Xi≤21\leq X_i\leq 2
  • 恰好有 AA 个 ii 满足 Xi=1X_i=1。
  • 恰好有 BB 个 ii 满足 Xi=2X_i=2。
  • 每次进行 Xi=2X_i=2 的操作前,ss 都不为空。
  • 输入的所有值均为整数。

样例解释 1

最终可能的 ss 集合有 s={1,2}s=\{1,2\} 和 s={1,3}s=\{1,3\} 共 22 种。例如,按如下方式操作,最终 s={1,3}s=\{1,3\}:

  • i=1i=1:向 ss 中加入 22。
  • i=2i=2:向 ss 中加入 11。
  • i=3i=3:从 ss 中删除 22。
  • i=4i=4:向 ss 中加入 33。