103215: [Atcoder]ABC321 F - #(subset sum = K) with Add and Erase

Problem Statement

We have a box, which is initially empty.
Let us perform a total of $Q$ operations of the following two types in the order they are given in the input.

+ $x$

Type $1$: Put into the box a ball with the integer $x$ written on it.

- $x$

Type $2$: Remove from the box a ball with the integer $x$ written on it.
It is guaranteed that the box contains a ball with the integer $x$ written on it before the operation.

For the box after each operation, solve the following problem.

Find the number, modulo $998244353$, to pick up some number of balls from the box so that the integers written on them sum to $K$.
All balls in the box are distinguishable.

Constraints

• All input values are integers.
• $1 \le Q \le 5000$
• $1 \le K \le 5000$
• For each type-$1$ operation, $1 \le x \le 5000$.
• All the operations satisfy the condition in the problem statement.

Input

The input is given from Standard Input in the following format, where $\mathrm{Query}_i$ represents the $i$-th operation:

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

Output

Print $Q$ lines.
The $i$-th line should contain the answer when the first $i$ operations have been done.

Sample Input 1

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

Sample Output 1

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

This input contains $15$ operations.

After the last operation, the box contains the balls $(5,10,1,3,1,7,4)$.
There are five ways to pick up balls for a sum of $10$:

• $5+1+3+1$ (the $1$-st, $3$-rd, $4$-th, $5$-th balls)
• $5+1+4$ (the $1$-st, $3$-rd, $7$-th balls)
• $5+1+4$ (the $1$-st, $5$-th, $7$-th balls)
• $10$ (the $2$-nd ball)
• $3+7$ (the $4$-th, $6$-th balls)

问题描述

我们有一个盒子，最初是空的。

让我们按照输入给出的顺序，对以下两种类型的总共$Q$个操作进行操作。

+ $x$

类型$1$：将写有整数$x$的球放入盒子中。

- $x$

类型$2$：从盒子中取出写有整数$x$的球。
保证在操作之前，盒子中包含一个写有整数$x$的球。

对于每次操作后的盒子，解决以下问题。

求从盒子中取出一些球，使它们上面写的整数之和为$K$的方案数，模$998244353$。
盒子里的球都是可区分的。

限制条件

• 所有输入值都是整数。
• $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$个，第$3$个，第$4$个，第$5$个球）
• $5+1+4$（第$1$个，第$3$个，第$7$个球）
• $5+1+4$（第$1$个，第$5$个，第$7$个球）
• $10$（第$2$个球）
• $3+7$（第$4$个，第$6$个球）