#P18682. Expression 3

    ID: 18018 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000NOI/NOI+/CTS贡献法双射计数期望线性性离散对数卷积转化NTT任意模数卷积中国剩余定理线性筛最小质因子预处理快速幂

Expression 3

Expression 3

小青鱼有 nn 个数 a1,a2,…,ana_1,a_2,\ldots,a_n 和 n−1n-1 个运算符 op1,op2,…,opn−1op_1,op_2,\ldots,op_{n-1}。每个运算符都是 + 或 -,它们按下面的形式排列:

a1 op1 a2 op2 a3 ⋯ opn−1 an.a_1\ op_1\ a_2\ op_2\ a_3\ \cdots\ op_{n-1}\ a_n.

他希望逐步消去这些数。第 ii 轮开始时,还剩 n+1−in+1-i 个数。他可以选择两个相邻的数,将这两个数及它们之间的运算符擦去,再把执行这次运算得到的新数放回原来的位置。

经过 n−1n-1 轮后,只剩一个数。这个数称为该操作序列的结果。

请你求出所有不同操作序列的结果之和。答案可能很大,输出它对 998244353998244353 取模的结果。当且仅当存在某一轮选择合并的两个数(在当时序列中的位置)不同,两个操作序列才视为不同。

输入格式

第一行包含一个整数 nn,满足 2≤n≤2×1052\le n\le2\times10^5。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 0≤ai≤1090\le a_i\le10^9。

第三行包含一个长度恰好为 n−1n-1 的字符串,仅由 +、- 组成,表示原来的运算符序列。

输出格式

输出一个整数,表示所有不同操作序列的结果之和对 998244353998244353 取模的结果。

样例 1 输入

4
9 1 4 1
-+-

样例 1 输出

46

样例 2 输入

5
1 2 3 4 5
+-+-

样例 2 输出

998244313

样例解释

样例 1 共有六种消去方式,以下每条箭头表示合并一对相邻的数与中间的运算符:

  1. $9-1+4-1\Rightarrow8+4-1\Rightarrow12-1\Rightarrow11$;
  2. 9−1+4−1⇒8+4−1⇒8+3⇒119-1+4-1\Rightarrow8+4-1\Rightarrow8+3\Rightarrow11;
  3. 9−1+4−1⇒9−5−1⇒4−1⇒39-1+4-1\Rightarrow9-5-1\Rightarrow4-1\Rightarrow3;
  4. 9−1+4−1⇒9−5−1⇒9−4⇒59-1+4-1\Rightarrow9-5-1\Rightarrow9-4\Rightarrow5;
  5. 9−1+4−1⇒9−1+3⇒8+3⇒119-1+4-1\Rightarrow9-1+3\Rightarrow8+3\Rightarrow11;
  6. 9−1+4−1⇒9−1+3⇒9−4⇒59-1+4-1\Rightarrow9-1+3\Rightarrow9-4\Rightarrow5。

因此答案为 11+11+3+5+11+5=4611+11+3+5+11+5=46。