/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
箱を用意します。最初、箱は空です。
この箱に対して、以下の 2 種類の操作を合計 Q 個、入力で与えられた順に施します。
+ x
タイプ 1 : 箱の中に整数 x の書かれたボールを 1 つ追加する。
- x
タイプ 2 : 箱の中にある、整数 x の書かれたボールを 1 つ取り除く。
但し、取り除く前の時点で箱の中に整数 x が書かれたボールが含まれることが保証されます。
各操作後の箱に関して、以下の問題を解いてください。
箱からボールをいくつか取り出して、ボールに書かれた整数の総和を K とする方法の総数を 998244353 で割った余りを求めてください。
但し、箱の中に入っている全てのボールは区別可能です。
制約
- 入力は全て整数
- 1 \le Q \le 5000
- 1 \le K \le 5000
- タイプ 1 の操作に関して、 1 \le x \le 5000
- 全ての操作は問題文中の条件を満たす。
入力
入力は以下の形式で標準入力から与えられる。
但し、 \rm{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 通りです。
- 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 番目のボールを取り出す )
Score : 525 points
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)