2025 河南省赛——Gym-105941-Problem B. 随机栈 II · znzryb
## 题目大意
**题目描述**
维护一个初始为空的多重集。每次从中取出一个元素时,集合中每个元素被取出的概率均等,取出后该元素从集合中删除。每次取出事件相互独立。
给定 $n$ 次操作序列,操作分为两种:
1. 向集合中插入一个给定的非负整数。
1. 从集合中随机取出一个元素。
保证每次取出时集合非空,且整个操作序列至少包含一次取出操作。
求所有被取出的元素排成的序列满足**单调不降**(即序列中每一项都小于等于它的后一项)的概率。答案对 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。
## 思路讲解

这道题目其实不难,就是细节比较多。
```cpp
for (ll op = 1; op <= cnt_op; ++op) {
vector<ll> vals;
for (int val = 0; val <= N; ++val) {
if (op_val_cnt[op][val] >= 1) {
vals.push_back(val);
}
}
if (op == 1) {
for (auto val: vals) {
dp_val_cnt[val].resize(2);
// 注意,有多个数字可选的时候,有多种可能,答案不是 1
dp_val_cnt[val][1] = op_val_cnt[op][val];
dpacc_val[val] = op_val_cnt[op][val];
}
} else {
vector<vector<ll> > ndp_val_cnt(N + 2);
vector<ll> ndpacc_val(N + 2);
vector<ll> presum_dpacc(N + 2);
// 注意使用前缀和优化
partial_sum(all(dpacc_val), presum_dpacc.begin(), [](ll a, ll b) {
return (a + b) % mod;
});
for (auto val: vals) {
ll val_cnt = op_val_cnt[op][val];
ndp_val_cnt[val].resize(min(op, val_cnt) + 2);
for (int cnt = 1; cnt <= min(op, val_cnt); ++cnt) {
ll rem_val = val_cnt - cnt + 1;
if (cnt >= 2) {
if (cnt - 1 > SZ(dp_val_cnt[val]) - 1) {
break;
}
ndp_val_cnt[val][cnt] = rem_val * dp_val_cnt[val][cnt - 1];
ndp_val_cnt[val][cnt] %= mod;
} else {
// for (int s_val = 0; s_val < val; ++s_val) {
// ndp_val_cnt[val][cnt] += dpacc_val[s_val];
// ndp_val_cnt[val][cnt] %= mod;
// }
if (val - 1 >= 0) {
ndp_val_cnt[val][cnt] = presum_dpacc[val - 1];
}
ndp_val_cnt[val][cnt] *= rem_val;
ndp_val_cnt[val][cnt] %= mod;
}
ndpacc_val[val] += ndp_val_cnt[val][cnt];
ndpacc_val[val] %= mod;
}
}
swap(dp_val_cnt, ndp_val_cnt);
swap(dpacc_val, ndpacc_val);
}
}
```
## AC代码
AC
[https://codeforces.com/gym/105941/submission/367931586](https://codeforces.com/gym/105941/submission/367931586)
::: 源代码
```cpp
/**
* Problem: 随机栈 II
* Contest: Gym
* Judge: Virtual Judge
* URL: https://vjudge.net/problem/Gym-105941B#author=user:262248
* Created: 2026-03-23 21:30:31
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
// 在 k<=0 的时候返回 1
ll binpow(ll a, ll k, const ll &p = mod) {
ll res = 1;
a %= p;
while (k > 0) {
if ((k & 1) == 1) res = a * res % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void Solve() {
ll N;
cin >> N;
vector<ll> A(N + 2);
for (int i = 1; i <= N; ++i) {
cin >> A[i];
}
ll cnt_op = count(all(A), -1);
vector<vector<ll> > op_val_cnt(cnt_op + 2, vector<ll>(N + 2));
ll tot_num = 1;
do {
ll opc = 0, numc = 0;
vector<ll> cnt(N + 2);
for (int i = 1; i <= N; ++i) {
if (A[i] == -1) {
tot_num *= (numc - opc);
tot_num %= mod;
opc++;
op_val_cnt[opc] = cnt;
} else {
cnt[A[i]]++;
numc++;
}
}
} while (false);
vector<vector<ll> > dp_val_cnt(N + 2);
vector<ll> dpacc_val(N + 2);
for (ll op = 1; op <= cnt_op; ++op) {
vector<ll> vals;
for (int val = 0; val <= N; ++val) {
if (op_val_cnt[op][val] >= 1) {
vals.push_back(val);
}
}
if (op == 1) {
for (auto val: vals) {
dp_val_cnt[val].resize(2);
dp_val_cnt[val][1] = op_val_cnt[op][val];
dpacc_val[val] = op_val_cnt[op][val];
}
} else {
vector<vector<ll> > ndp_val_cnt(N + 2);
vector<ll> ndpacc_val(N + 2);
vector<ll> presum_dpacc(N + 2);
partial_sum(all(dpacc_val), presum_dpacc.begin(), [](ll a, ll b) {
return (a + b) % mod;
});
for (auto val: vals) {
ll val_cnt = op_val_cnt[op][val];
ndp_val_cnt[val].resize(min(op, val_cnt) + 2);
for (int cnt = 1; cnt <= min(op, val_cnt); ++cnt) {
ll rem_val = val_cnt - cnt + 1;
if (cnt >= 2) {
if (cnt - 1 > SZ(dp_val_cnt[val]) - 1) {
break;
}
ndp_val_cnt[val][cnt] = rem_val * dp_val_cnt[val][cnt - 1];
ndp_val_cnt[val][cnt] %= mod;
} else {
// for (int s_val = 0; s_val < val; ++s_val) {
// ndp_val_cnt[val][cnt] += dpacc_val[s_val];
// ndp_val_cnt[val][cnt] %= mod;
// }
if (val - 1 >= 0) {
ndp_val_cnt[val][cnt] = presum_dpacc[val - 1];
}
ndp_val_cnt[val][cnt] *= rem_val;
ndp_val_cnt[val][cnt] %= mod;
}
ndpacc_val[val] += ndp_val_cnt[val][cnt];
ndpacc_val[val] %= mod;
}
}
swap(dp_val_cnt, ndp_val_cnt);
swap(dpacc_val, ndpacc_val);
}
}
ll tot_dp_cnt = 0;
for (int val = 0; val <= N; ++val) {
for (int cnt = 1; cnt < SZ(dp_val_cnt[val]); ++cnt) {
tot_dp_cnt += dp_val_cnt[val][cnt];
tot_dp_cnt %= mod;
}
}
ll ans = tot_dp_cnt * binpow(tot_num, mod - 2);
ans %= mod;
cout << ans << "\n";
// #ifdef LOCAL
// debug(tot_dp_cnt);
// debug(tot_num);
// debug2d(dp_val_cnt);
// #endif
// mod
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/105941/submission/367931586
1
3
1 2 -1
*/
```
:::
## 心路历程(WA,TLE,MLE……)
```cpp
do {
// 注意,还是要把 numc 显式地写出来
ll opc = 0, numc = 0;
vector<ll> cnt(N + 2);
for (int i = 1; i <= N; ++i) {
if (A[i] == -1) {
tot_num *= (numc - opc);
tot_num %= mod;
opc++;
op_val_cnt[opc] = cnt;
} else {
cnt[A[i]]++;
numc++;
}
}
} while (false);
```