Problem Statement
随机栈 Toxel 获得了一个随机的 “栈”。这个栈可被视为一个 多 重 集 S，从一个非空的随机栈 S 中取出一个 元素时，有可能从中取出任何一个元素，其中每个元素被取出的概率是相等的。取出该元素后，该元素会 从集合中删除。以{1,2,2} 为例，有 1/3 的概率取出1，使得集合变为{2,2}，有 2/3 的概率取出2，使得集 合变为{1,2}。每次取出元素的事件相互独立。 Toxel 正在对这个集合做一些操作。集合初始时为空，它总共进行了2n次操作，其中n次操作为插 入，n次操作为取出。现在，Toxel告诉了你它操作的顺序以及每次插入的数，且保证每次取出时，集合 非空。Toxel 想知道，如果把每次取出的数排成一个序列，那么这个序列递增的概率是多少？这里，递增 的严格定义是：取出数列的每一项（除最后一项）.小.于.等 .于它的后一项。 由于答案可能不是整数，为了方便计算，你只需要求出这个值对998244353取模的结果。
第一行包含一个整数n（1 ≤ n ≤ 2×10e5）。 第二行包含2n个整数a1,a2,…,a2n（−1 ≤ ai ≤ n），表示 Toxel 操作的序列。其中，若0 ≤ ai ≤ n， 表示Toxel 向集合中插入了ai；否则ai=−1，表示Toxel从集合中取出了一个元素。数据保证取出元素 时，集合非空；保证插入和取出操作的次数分别为n
Output
输出一行一个整数，表示答案对998244353取模的结果
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
// 除法同余（乘法逆元）
int qpow(int x,int y)
{
int res = 1;
while(y>0)
{
if(y&1) res = (res * x) % MOD;
x = (x * x) % MOD;
y >>= 1;
}
return res;
}
int invfac(int x)
{
return qpow(x,MOD-2) % MOD;
}
int calcu(int p,int q)
{
return ((p % MOD)*(invfac(q))) % MOD;
}
void solve()
{
int n;
cin >> n;
map<int,int> mp;
int total = 1;
int res = 1;
priority_queue<int,vector<int>,greater<int>> q;
int x;
int lo = -1;
for(int i=1;i<=2*n;i++)
{
cin >> x;
if(x >= 0)
{
mp[x]++;
q.push(x);
}
if(x == -1)
{
// 样本空间更新
total = (total * q.size()) % MOD;
// 满足递增的空间
res = (res * mp[q.top()]) % MOD;
if(!q.empty()&&q.top() >= lo)
{
lo = q.top();
mp[q.top()]--;
q.pop();
}
else
{
cout << 0 << endl;
return;
}
}
}
cout << calcu(res,total) % MOD;
}
|