← 返回题目列表

AtCoder · past202309_n

N. 种类和功能

中文机器翻译题面 查看原题

问题陈述

对于多重集(允许包含重复元素的集) S 正整数,让我们定义函数 f(S) 如下。

  • 首先,让 A=(A_0,A_1,...,A_{|S|-1}) 是元素的排序列表 S 按升序排列。
  • 然后,让 f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i。这个常数 K 由输入给出。
  • 在这里,让 f(S)=0 if S 为空。

有一个最初为空的多重集 T。让我们对此集合执行以下操作 总共 Q 次。

+ X

添加一个实例 x to T.

- x

删除一个实例 x 来自 T。保证至少有一个实例 x 存在于 T 此时。

每次操作后,查找 f(T) 模数 998244353 当时。

约束

  • Q 和 K 是整数。
  • 1 \le Q \le 3 \times 10^5
  • 1 \le K < 998244353
  • 对于每个操作, x 是一个整数。
  • 对于每个操作 +, 1 \le x < 998244353.
  • 对于每个操作 -,有一个或多个实例 x in T 当时。

输入

输入由标准输入按以下格式给出:

Q K
ope_1
ope_2
\vdots
ope_Q

在这里, ope_i 代表 i要执行的第一个操作。

输出

打印 您选择的 Q 行。
的 i- 第行应包含以下值 f(T) 模数 998244353 在末尾 i第次操作。


示例输入 1

10 2
+ 7
- 7
+ 2
+ 3
- 2
+ 3
+ 5
- 3
+ 998244352
+ 5

示例输出 1

7
0
2
8
3
9
29
13
9
25
  • 第一个操作添加一个实例 7 to T.
    • 现在, 给出了 T=\{7\} 和 f(T)=7.
  • 第二个操作删除一个实例 7 来自 T.
    • 现在, 给出了 T=\{\} 和 f(T)=0.
  • 第三个操作添加一个实例 2 to T.
    • 现在, 给出了 T=\{2\} 和 f(T)=2.
  • 第四个操作添加一个实例 3 to T.
    • 现在, 给出了 T=\{2,3\} 和 f(T)=8.
  • 第五个操作删除一个实例 2 来自 T.
    • 现在, 给出了 T=\{3\} 和 f(T)=3.
  • 第六个操作添加一个实例 3 to T.
    • 现在, 给出了 T=\{3,3\} 和 f(T)=9.
  • 第七个操作添加一个实例 5 to T.
    • 现在, 给出了 T=\{3,3,5\} 和 f(T)=29.
  • 第八个操作删除一个实例 3 来自 T.
    • 现在, 给出了 T=\{3,5\} 和 f(T)=13.
  • 第九个操作添加一个实例 998244352 to T.
    • 现在, 给出了 T=\{3,5,998244352\} 和 f(T)=3992977421,所以打印这个模 998244353,即 9.
  • 第十个操作添加一个实例 5 to T.
    • 现在, 给出了 T=\{3,5,5,998244352\} 和 f(T)=7985954849,所以打印这个模 998244353,即 25.