← 返回题目列表

AtCoder · arc127_e

E. 优先队列

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给定的是一系列 A+B 整数 (X_1,X_2,\cdots,X_{A+B}),其中恰好包含 A 和完全一样 B 两点。

Snuke 有一套 s,最初是空的。 他要做的 A+B 操作。 的 i第操作如下。

  • If X_i=1: 选择一个整数 v 这样 1 \leq v \leq A 并将其添加到 s。 在这里, v 不得是在先前操作中选择的整数。

  • If X_i=2:删除自 s 具有最大值的元素。 输入保证 在此操作之前 s 不为空。

有多少组可以成为最终状态 s? 求计数模数 998244353.

约束

  • 1 \leq A \leq 5000
  • 0 \leq B \leq A-1
  • 1 \leq X_i \leq 2
  • X_i=1 正是 A 指数 i.
  • X_i=2 正是 B 指数 i.
  • s 在执行以下操作之前不会为空 X_i=2.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

A B
X_1 X_2 \cdots X_{A+B}

输出

打印答案模数 998244353.


样本输入 1

3 1
1 1 2 1

示例输出 1

2

有两种可能的最终状态 s: s=\{1,2\},\{1,3\}.

例如,以下操作序列会产生 s=\{1,3\}.

  • i=1:添加 2 to s.
  • i=2:添加 1 to s.
  • i=3:删除 2 来自 s.
  • i=4:添加 3 to s.

示例输入 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