Score : $525$ points

问题描述

我们有一个盒子，最初是空的。 现在按照输入中给出的顺序执行总共 $Q$ 个以下两种类型的操作：

$+ \ x$

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

$-\ x$

类型 2：从盒子中移除一个写有整数 $x$ 的球。 保证在执行该操作之前，盒子里一定包含一个写有整数 $x$ 的球。

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

求出（模 $998244353$）从盒子中取出若干个球，使得这些球上所写的整数之和为 $K$ 的取法数目。 盒子中的所有球都是可区分的。

以上为通义千问 qwen-max 翻译，仅供参考。

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)

update @ 2024/3/10 01:41:10