2025 河南省赛——Problem B. 随机栈 II

题目大意

题目描述
维护一个初始为空的多重集。每次从中取出一个元素时，集合中每个元素被取出的概率均等，取出后该元素从集合中删除。每次取出事件相互独立。
给定 $n$ 次操作序列，操作分为两种：

1. 向集合中插入一个给定的非负整数。

2. 从集合中随机取出一个元素。
   保证每次取出时集合非空，且整个操作序列至少包含一次取出操作。
   求所有被取出的元素排成的序列满足单调不降（即序列中每一项都小于等于它的后一项）的概率。答案对 998244353 取模。

输入格式
第一行包含一个正整数 $T$（$1 \le T \le 2.5 \times 10^3$），表示测试数据组数。
每组数据第一行包含一个整数 $n$（$2 \le n \le 5 \times 10^3$），表示操作总数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-1 \le a_i \le n$），表示操作序列：

• $a_i \ge 0$ 表示向集合中插入 $a_i$。

• $a_i = -1$ 表示从集合中随机取出一个元素。
  保证所有数据的 $\sum n \le 5 \times 10^3$。

输出格式
对于每组数据，输出一行一个整数，表示概率对 998244353 取模的结果。

样例输入 1

3
3
1 2 -1
5
1 2 -1 3 -1
7
1 2 3 4 -1 -1 -1

样例输出 1

1
249561089
166374059

样例输入 2

3
4
1 2 -1 -1
6
1 2 -1 -1 1 -1
8
1 -1 2 -1 3 -1 4 -1

样例输出 2

499122177
0
1

样例解释
对于样例一的第 1 组数据，由于总共只取出了一个元素，序列无论如何都是单调不降的，概率为 1。

对于样例一的第 2 组数据，操作过程和对应概率如下：

• 加入 1，集合变为 $\{1\}$；加入 2，集合变为 $\{1, 2\}$。

• 此时取出 1 的概率为 $\frac{1}{2}$。若取出 1，接下来加入 3，集合变为 $\{2, 3\}$。之后无论取出哪个数，得到的序列（1 然后是 2 或 1 然后是 3）均满足单调不降。此情况的合法概率为 $\frac{1}{2} \times 1 = \frac{1}{2}$。

• 此时取出 2 的概率为 $\frac{1}{2}$。若取出 2，接下来加入 3，集合变为 $\{1, 3\}$。之后为了保持单调不降，必须取出 3，取出 3 的概率为 $\frac{1}{2}$。此情况的合法概率为 $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$。
  最终单调不降的总概率为 $\frac{1}{2} + \frac{1}{4} = \frac{3}{4}$。$\frac{3}{4}$ 对 998244353 取模的结果为 249561089。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）