Priority Queue
题意翻译
给定一个序列 $A$，$A$ 的每一个元素形如 `+ x` 和 `-`，其中 $x$ 为一个整数。
对于一个每个元素都形如 `+ x` 和 `-` 的序列 $S$，按如下方式计算 $f(S)$ 的值：
- 你需要依次遍历 $S$ 中的元素，并且维护一个可重集 $T$。
- 对于每个 $S$ 中的元素，若其为 `+ x`，那么就将 $x$ 加入 $T$，否则就删除 $T$ 最小的数。特别的，若 $T$ 中没有数，那么就不进行删除操作。
- 在遍历完 $S$ 中的元素后，将可重集 $T$ 中所有数的和 $sum$ 算出来。$sum$ 即为 $f(S)$ 的值。
定义 $b$ 是 $a$ 的子序列当且仅当 $b$ 是由 $a$ 在不改变原有顺序的情况下删除若干元素得到的。现在对于 $A$ 的所有子序列 $B$，蓝想让你求出 $f(B)$ 的和模 $998244353$ 的值。
本题有 $1 \leq n \leq 500$，并且对于每个形如 `+ x` 元素中的 $x$，有 $1 \leq x < 998244353$。
题目描述
You are given a sequence $ A $ , where its elements are either in the form + x or -, where $ x $ is an integer.
For such a sequence $ S $ where its elements are either in the form + x or -, define $ f(S) $ as follows:
- iterate through $ S $ 's elements from the first one to the last one, and maintain a multiset $ T $ as you iterate through it.
- for each element, if it's in the form + x, add $ x $ to $ T $ ; otherwise, erase the smallest element from $ T $ (if $ T $ is empty, do nothing).
- after iterating through all $ S $ 's elements, compute the sum of all elements in $ T $ . $ f(S) $ is defined as the sum.
The sequence $ b $ is a subsequence of the sequence $ a $ if $ b $ can be derived from $ a $ by removing zero or more elements without changing the order of the remaining elements. For all $ A $ 's subsequences $ B $ , compute the sum of $ f(B) $ , modulo $ 998\,244\,353 $ .
输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1\leq n\leq 500 $ ) — the length of $ A $ .
Each of the next $ n $ lines begins with an operator + or -. If the operator is +, then it's followed by an integer $ x $ ( $ 1\le x<998\,244\,353 $ ). The $ i $ -th line of those $ n $ lines describes the $ i $ -th element in $ A $ .
输出格式
Print one integer, which is the answer to the problem, modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
4
-
+ 1
+ 2
-输出样例 #1
16输入样例 #2
15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-输出样例 #2
750759115说明
In the first example, the following are all possible pairs of $ B $ and $ f(B) $ :
- $ B= $ {}, $ f(B)=0 $ .
- $ B= $ {-}, $ f(B)=0 $ .
- $ B= $ {+ 1, -}, $ f(B)=0 $ .
- $ B= $ {-, + 1, -}, $ f(B)=0 $ .
- $ B= $ {+ 2, -}, $ f(B)=0 $ .
- $ B= $ {-, + 2, -}, $ f(B)=0 $ .
- $ B= $ {-}, $ f(B)=0 $ .
- $ B= $ {-, -}, $ f(B)=0 $ .
- $ B= $ {+ 1, + 2}, $ f(B)=3 $ .
- $ B= $ {+ 1, + 2, -}, $ f(B)=2 $ .
- $ B= $ {-, + 1, + 2}, $ f(B)=3 $ .
- $ B= $ {-, + 1, + 2, -}, $ f(B)=2 $ .
- $ B= $ {-, + 1}, $ f(B)=1 $ .
- $ B= $ {+ 1}, $ f(B)=1 $ .
- $ B= $ {-, + 2}, $ f(B)=2 $ .
- $ B= $ {+ 2}, $ f(B)=2 $ .
The sum of these values is $ 16 $ .