← 返回题目列表

AtCoder · abc321_f

I. #(子集和 = K) 带添加和擦除

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

分数: 525 点

问题陈述

我们有一个盒子,最初是空的。
让我们总共执行 Q 以下两种类型的操作(按照输入中给出的顺序排列)。

+ x

类型 1: 将一个带有整数的球放入盒子中 上面写着 x 。

- x

类型 2:从盒子中取出一个带有整数的球 x 。
保证盒子里有一个带有整数的球 操作前写上 x 。


对于每次操作后的框,解决以下问题。

求模数 998244353,从盒子里拿起一定数量的球,以便球上写的整数之和为 K.
盒子里的所有球都是可区分的。

约束

  • 所有输入值均为整数。
  • 1 \le Q \le 5000
  • 1 \le K \le 5000
  • 对于每种类型 -1 操作, 1 \le x \le 5000.
  • 所有操作都满足问题陈述中的条件。

输入

输入由标准输入按以下格式给出,其中 \mathrm{Query}_i 代表 i-第操作:

Q K
\rm{Query}_{1}
\rm{Query}_{2}
\vdots
\rm{Query}_{Q}

输出

打印 Q 行。
的 i第一行应包含第一行时的答案 i 操作已完成。


示例输入 1

15 10
+ 5
+ 2
+ 3
- 2
+ 5
+ 10
- 3
+ 1
+ 3
+ 3
- 5
+ 1
+ 7
+ 4
- 3

示例输出 1

0
0
1
0
1
2
2
2
2
2
1
3
5
8
5

该输入包含 15 操作。

最后一次操作后,盒子里有球 (5,10,1,3,1,7,4).
有五种方法可以拾取球,总金额为 10:

  • 5+1+3+1 ( 1-st, 3-rd, 4-th, 5第个球)
  • 5+1+4 ( 1-st, 3-rd, 7第个球)
  • 5+1+4 ( 1-st, 5-th, 7第个球)
  • 10 ( 2-nd 球)
  • 3+7 ( 4-th, 6第个球)