分数: 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第个球)