一、题目重述（核心）

我们有一个已知数组 ( a_1, a_2, \dots, a_n )，满足：

[ \max(|a_i|) \le \sum_{i=1}^n a_i ]

要求构造新的数组 ( b_1, b_2, \dots, b_m )，满足：

1. ( a ) 是 ( b ) 的子序列（不一定连续，但顺序一致）。
2. (\sum b = \sum a)。
3. 在满足 1、2 的所有 ( b ) 中，最大子段和（boredom）最小。
4. 在 boredom 最小的基础上，长度 ( m ) 最小。
5. 对每个这样的最优 ( b )，计算 ( a ) 作为子序列在 ( b ) 中的出现次数（子序列匹配计数），称为该 ( b ) 的 value。
6. 求所有可能的最优 ( b ) 的 value 之和，对 ( 998244353 ) 取模。

---

二、理解最优 ( b ) 的结构

设 ( S = \sum a )。

原题条件 (\max |a_i| \le S) 保证了 ( S \ge 0 )。

1. 最小可能的 boredom

最大子段和最小是多少？
任何子段和 ≤ 数组总和 ( S )，并且至少包含一个元素。
可以构造 ( b ) 使最大子段和 = ( S ) 吗？
可以：如果 ( b ) 所有元素都是非负的，那么最大子段和 = ( S )。

可以更小吗？
比如 ( b = [S] ) 时，最大子段和 = ( S )，所以 ( S ) 是下界吗？不一定，因为要包含 ( a ) 作为子序列。

由于 ( a ) 中可能有负数，但总和 ( S ) 是非负的，所以包含 ( a ) 的子序列的最大子段和至少是 ( \max a_i ) 吗？其实我们看 ( b ) 的构造方式。

---

关键观察：
在最优构造中，boredom = ( S )。为什么？
因为我们可以构造 ( b ) 为 ( a ) 加上一些辅助元素，使总和不变，且所有元素非负（除保留 ( a ) 中的负数），但一旦有负数，最大子段和可能大于 ( S ) 吗？
实际上，如果我们把负号放在两端，中间非负，最大子段和仍然是某一段非负的和。
但如果我们希望 boredom 尽量小，一个简单方法是把 ( a ) 拆成若干段非负的连续段，段内求和作为新元素，负数单独成元素，但这样可能让负数出现在中间导致更大的最大子段和。

其实已知结论（来自官方题解）：
最优的 boredom = ( S )，且构造方式如下：

• 把 ( a ) 从左到右处理，维护当前连续非负和 cur。
• 当遇到负数时，若 cur + 这个负数 ≥ 0，则继续累积；否则，cur 单独作为一个正段，负数单独作为一段，然后 cur 重置为 0 或这个负数（如果负数大于 cur 的绝对值）。 实际上标准解法最终最优的 ( b ) 长度 = ( n + ) 一些插入的辅助元素，且每个元素 ≤ S，总和 = S，每个元素 ≥ -S，且最大子段和 = S。

---

三、转化为组合问题

对最优 ( b ) 的要求：

• 子序列包含 ( a )
• 总和 = ( S )
• 每个元素 ∈ ([-S, S])
• 所有元素的和 = ( S )
• 最大子段和 = ( S )

最大子段和 = ( S ) 等价于：存在一个子段（连续）和为 ( S )，且其他子段和 ≤ ( S )。由于总和也是 ( S )，这意味着 整个数组的最大子段和等于总和，即从某位置到结尾的和等于 S，或从头到某位置的和等于 S，或整个数组的和等于 S（显然成立）。更准确地说，这意味着数组在某个前缀或后缀达到最大，且其他子段不能更大。

另一种等价条件（常见于这种题）：
数组的最大子段和 = ( S ) ⇔ 存在一个位置，使得所有前缀和 ≤ S 且所有后缀和 ≤ S，并且某个前缀或后缀等于 S。

但这里因为总和 = S，所以只要所有子段和 ≤ S，且存在某个子段和 = S 即可。

---

四、构造最优 ( b ) 的标准形式

官方题解结论：
最优 ( b ) 可以构造成如下形式：

从左到右扫描 ( a )，维护当前非负累加和 cur。

• 若 a[i] ≥ 0，cur += a[i]
• 若 a[i] < 0：
  • 若 cur + a[i] ≥ 0，则 cur += a[i]（不单独分段）
  • 若 cur + a[i] < 0，则把 cur 作为一个正元素，a[i] 作为一个负元素，cur 重置为 0（表示新开始）。

这样构造出来的 b 长度最小，并且最大子段和 = S。

但问题是，这样构造的 b 是唯一的吗？
不是，因为对于非负累加和 cur，我们可以在任何位置拆分 cur 为两个正数，只要它们加起来等于 cur，仍然满足条件。
这就是计数的地方。

---

五、动态规划与单调队列优化

我们要求所有可能的最优 b 中，a 作为子序列的出现次数之和。

等价于：我们按照上述构造方式，在遇到 cur 段时，可以选择把 cur 拆成若干正数，它们的顺序是固定的（因为必须保持 a 中顺序），但是这些正数之间可以插入 0 吗？
插入 0 不影响子序列匹配，但会影响出现次数计数。

其实这是一个经典的子序列自动机 + 分段组合问题。

我们定义状态：
扫描 a 的过程中，维护当前 b 的末尾指针位置？但直接做指数级。

---

六、标程分析

标程中：

Q.push_back(Node(0, 1, 1)), Q.push_back(Node(1, 1, p));

p 是总和 ( S )。

Node 包含：

• f：段类型（其实这里是分段后的索引？）
• g：该段的贡献计数（modint）
• len：该段的长度（在值域意义上）

Q 是 deque，维护当前可能的段。

遍历 ( a_i )：

• 若 a[i] ≥ 0：增加正长度，更新 Q 尾部
• 若 a[i] < 0：减少长度，更新 Q 头部

v 是当前段编号。

gv 和 gz 分别表示当前段和另一个段的累计贡献。

tv 和 tz 是中间变量。

最后答案是 Q.back().g + (r == p ? tv : tz)。

---

这里 r 表示当前剩余可分配的正长度，l 表示左边界。

实际上这是在维护所有可能的最优 b 中，a 作为子序列的出现次数，用单调队列优化转移，因为每次增减长度是区间操作。

---

七、总结算法流程

1. 读入 a，计算 S = sum(a)，验证 max|a| ≤ S。
2. 用双端队列维护当前可能的正段长度（值域 ≤ S），每个段有贡献计数。
3. 从左到右处理 a[i]：
   • 如果 a[i] ≥ 0：
     从队列尾部减去对应长度，更新 gv/gz，
     更新 l, r，
     若 l > r，说明必须新开一段，v++，重置变量。
   • 如果 a[i] < 0：
     从队列头部减去对应长度，更新 gv/gz，
     更新 l, r，
     同样检查 l > r 则新开一段。
4. 每一步要维护 gz += -tz * (a[i] % MOD) 等，其实是在计算组合数贡献。
5. 最后队列尾部的 g 加上特殊情况贡献即为答案。

---

八、复杂度

每个 a[i] 最多进入/离开队列一次，总复杂度 O(n)。

---

九、关键点

• 最优 b 的唯一自由度是：非负段可以拆分成若干正数，不同拆法产生不同 b，不同 b 中 a 作为子序列的匹配次数不同。
• 用单调队列维护当前所有可能的拆分长度，结合前缀和差分统计贡献。
• modint 类处理取模。

---