珍珠帝王蟹(Crab King)
题目背景
在一次航程中,你偶然发现了被一片礁石环绕的帝王蟹,被月岛能量侵蚀的它又与月光有着怎样的联系呢?似乎只有击败它才能见分晓。
题目描述
帝王蟹可以通过镶嵌宝石触发战斗,不同的宝石效果不同,但奇特的是,镶嵌宝石的顺序有时也会影响它的强度。
帝王蟹有一个初始为 $0$ 的强度值,每个宝石有属性 $op$ 和 $v$,表示:
- 若 $op$ 为 `+`,则镶嵌后帝王蟹的强度值将会加上 $v$;
- 若 $op$ 为 `*`,则镶嵌后帝王蟹的强度值将会乘上 $v$。
由于宝石的效果十分奇异,所以 $v$ 可能是负数。
作为一个有挑战精神的冒险者,你希望采取某种镶嵌方式,将**每个宝石**都镶嵌**恰好一遍**,且使得帝王蟹的强度值最大。
你只需要输出最大的强度值对 $998244353$ 取模的结果,注意这是一个 $[0, 998244353)$ 中的数。
也就是说,如果答案为 `ans`,按照 C++ 语法,你需要输出 `(ans % P + P) % P`,其中 `P = 998244353`。
输入输出格式
输入格式
第一行,一个整数 $n$,表示宝石数量。
接下来 $n$ 行,每行有用空格隔开的一个字符 $op$ 和一个整数 $v$,描述一个宝石。
输出格式
输出一行一个整数,表示最大的强度值对 $998244353$ 取模的结果。
输入输出样例
输入样例 #1
3
+ -3
+ 4
* -4
输出样例 #1
16
输入样例 #2
3
+ -3
+ -4
* 4
输出样例 #2
998244346
说明
**【样例 1 解释】**
按照输入顺序以 $1, 2, 3$ 标记每个宝石,所有可能的镶嵌顺序如下:
$1\to 2\to 3$:$x = ((0 + {\color{red}{-3}}) + {\color{red}{4}}) \times {\color{red}{-4}} = -4$;
$1\to 3\to 2$:$x = ((0 + {\color{red}{-3}}) \times {\color{red}{-4}}) + {\color{red}{4}} = 16$;
$2\to 1\to 3$:$x = ((0 + {\color{red}{4}}) + {\color{red}{-3}}) \times {\color{red}{-4}} = -4$;
$2\to 3\to 1$:$x = ((0 + {\color{red}{4}}) \times {\color{red}{-4}}) + {\color{red}{-3}} = -19$;
$3\to 1\to 2$:$x = ((0 \times {\color{red}{-4}}) + {\color{red}{-3}}) + {\color{red}{4}} = 1$;
$3\to 2\to 1$:$x = ((0 \times {\color{red}{-4}}) + {\color{red}{4}}) + {\color{red}{-3}} = 1$。
因此,强度值的最大值为 $16$,对 $998244353$ 取模后为 $16$。
---
**【样例 2 解释】**
按照输入顺序以 $1, 2, 3$ 标记每个宝石,所有可能的镶嵌顺序如下:
$1\to 2\to 3$:$x = ((0 + {\color{red}{-3}}) + {\color{red}{-4}}) \times {\color{red}{4}} = -28$;
$1\to 3\to 2$:$x = ((0 + {\color{red}{-3}}) \times {\color{red}{4}}) + {\color{red}{-4}} = -16$;
$2\to 1\to 3$:$x = ((0 + {\color{red}{-4}}) + {\color{red}{-3}}) \times {\color{red}{4}} = -28$;
$2\to 3\to 1$:$x = ((0 + {\color{red}{-4}}) \times {\color{red}{4}}) + {\color{red}{-3}} = -19$;
$3\to 1\to 2$:$x = ((0 \times {\color{red}{4}}) + {\color{red}{-3}}) + {\color{red}{-4}} = -7$;
$3\to 2\to 1$:$x = ((0 \times {\color{red}{4}}) + {\color{red}{-4}}) + {\color{red}{-3}} = -7$。
因此,强度值的最大值为 $-7$,对 $998244353$ 取模后为 $998244346$。
---
**【数据范围】**
**本题采用捆绑测试。**
对于全部测试数据:$1 \le n \le {10}^5$,$2 \le |v| \le {10}^6$。
- Subtask 1(26 points):$n \le 9$,$|v| \le 5$。
- Subtask 2(22 points):$v > 0$。
- Subtask 3(12 points):保证当 $op$ 为 `*` 时 $v > 0$。
- Subtask 4(15 points):保证当 $op$ 为 `+` 时 $v > 0$。
- Subtask 5(25 points):无特殊限制。
---
![](https://cdn.luogu.com.cn/upload/image_hosting/rwzuwu9z.png)