AT_abc321_f [ABC321F] #(subset sum = K) with Add and Erase

题目描述

有一个箱子。最初，箱子是空的。
对这个箱子，总共要按输入给定的顺序进行 $2$ 种操作共 $Q$ 次。

+ $x$

类型 $1$：向箱子中加入一个写有整数 $x$ 的球。

- $x$

类型 $2$：从箱子中取出一个写有整数 $x$ 的球。
保证在取出前，箱子中一定存在一个写有整数 $x$ 的球。

对于每次操作后，请解决以下问题：

从箱子中取出若干个球，使得这些球上写的整数之和恰好为 $K$，共有多少种取法？请输出对 $998244353$ 取模的结果。
注意，箱子中的所有球都是可区分的。

输入格式

输入通过标准输入给出。
其中，$\rm{Query}_i$ 表示第 $i$ 次操作。

$Q$ $K$ $\rm{Query}_1$ $\rm{Query}_2$ $\vdots$ $\rm{Query}_Q$

输出格式

共输出 $Q$ 行。
第 $i$ 行输出进行到第 $i$ 次操作后时的答案。

输入输出样例 #1

输入 #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

说明/提示

限制条件

• 输入均为整数。
• $1\le Q\le 5000$
• $1\le K\le 5000$
• 对于类型 $1$ 的操作，$1\le x\le 5000$
• 所有操作均满足题目中的条件。

样例解释 1

本输入包含 $15$ 次操作。最后一次操作后，箱子中的球为 $(5,10,1,3,1,7,4)$。使总和为 $10$ 的取法有以下 $5$ 种：

• $5+1+3+1$（取第 $1,3,4,5$ 个球）
• $5+1+4$（取第 $1,3,7$ 个球）
• $5+1+4$（取第 $1,5,7$ 个球）
• $10$（取第 $2$ 个球）
• $3+7$（取第 $4,6$ 个球）

由 ChatGPT 4.1 翻译