F. 重构 – 详细题解

问题转化

设 $x_i = a_1 + a_2 + \dots + a_i$ 为前缀和，特别地 $x_0 = 0$，$x_n = S$ 为所有元素的和。
对于第 $i$ 个位置：

• 若 $s_i = \text{P}$，则 $b_i = x_i$。
• 若 $s_i = \text{S}$，则 $b_i = a_i + \dots + a_n = S - x_{i-1}$，即 $x_{i-1} = S - b_i$。

因此，每个约束都将某个 $x_j$ 表示为 $c_j S + d_j$ 的形式，其中 $c_j \in \{0,1\}$，$d_j$ 是整数常量。
初始已知 $x_0 = 0$，即 $(c_0,d_0)=(0,0)$；最终 $x_n = S$，即 $(c_n,d_n)=(1,0)$。

所有 $a_i = x_i - x_{i-1}$ 必须满足 $|a_i| \le m$，即 $|x_i - x_{i-1}| \le m$。
对于任意 $l < r$，由三角不等式可得 $|x_r - x_l| \le m \cdot (r-l)$. $\qquad (1)$

确定性与不定性

对于已经确定的 P 或 S，它们强制某个 $x_j$ 的具体表达式（即 $(c_j,d_j)$）。
对于 ?，我们可以选择将其解释为 P 或 S，从而在对应的位置添加强制点。
我们要统计所有选择，使得整个系统的约束（等式和不等式）有解。

关键思想

因为所有 $x_j$ 最终都是 $S$ 的线性函数，且 $|x_i - x_{i-1}| \le m$ 等价于任意两位置之间的 (1) 式成立，所以整个系统可解当且仅当：

1. 所有强制点（包括 $x_0$ 和 $x_n$）的表达式之间不冲突（同一位置不能有两个不同的 $(c,d)$）。
2. 对强制点按位置排序后，相邻两点之间的 (1) 式对 $S$ 给出的线性不等式有公共解（即所有区间的交集非空）。

因此，我们只需要维护当前已经出现的强制点序列以及 $S$ 的可行区间。每添加一个新强制点，就与上一个强制点通过 (1) 式更新区间，若更新后区间非空则状态合法。

动态规划设计

按位置从左到右处理 $i=1 \dots n$，维护最后一个强制点的信息：

• 其位置 $p$，
• 系数 $c \in \{0,1\}$，
• 常数 $d$，
• 当前 $S$ 的可行区间 $[L,R]$（闭区间，整数）。

初始状态：$(p=0,\; c=0,\; d=0,\; L=-\infty,\; R=+\infty)$，方案数为 $1$。

转移时根据 $s_i$：

• 如果 $s_i = \text{P}$：只能选择 P，因此新强制点为 $(i,\;0,\;b_i)$。设上一个强制点为 $(p,c,d)$，计算差 $\Delta c = 0 - c$，$\Delta d = b_i - d$，步长 $\Delta i = i - p$。
  代入 (1) 得到关于 $S$ 的不等式
  $|\,\Delta c \cdot S + \Delta d\,| \le m \cdot \Delta i$.
  若 $\Delta c = 0$，则要求 $|\Delta d| \le m\Delta i$，否则区间不变；
  若 $\Delta c = 1$，则 $-m\Delta i \le S + \Delta d \le m\Delta i$，即 $S \in [-m\Delta i - \Delta d,\; m\Delta i - \Delta d]$；
  若 $\Delta c = -1$，则 $S \in [\Delta d - m\Delta i,\; \Delta d + m\Delta i]$。
  将求出的区间与当前 $[L,R]$ 取交集，若新区间非空，则新状态 $(i,0,b_i, L',R')$ 继承方案数。

• 如果 $s_i = \text{S}$：只能选择 S，新强制点为 $(i-1,\;1,\;-b_i)$。注意必须保证 $i-1 > p$，否则强制点顺序错乱（后出现的强制点位置必须更大）。然后同样计算 $\Delta c = 1-c$，$\Delta d = -b_i - d$，$\Delta i = (i-1)-p$，更新区间并产生新状态。

• 如果 $s_i = \text{?}$：两种选择均可，分别按照上述规则生成两个新状态，方案数累加。

由于 $n \le 2000$ 且总 $n$ 之和 $\le 5000$，状态总数可控。实际实现中，每个状态用 $(p,c,d,L,R)$ 唯一标识，使用 map 存储方案数。每次转移时，遍历当前所有状态，对每个状态产生 $1$ 或 $2$ 个后继，并将相同后继的状态合并（方案数相加）。

最终处理

处理完所有 $i$ 后，我们还需要强制加入终点强制点 $(n,\;1,\;0)$，因为 $x_n=S$ 必须成立。
对于每个剩余状态，用它作为上一个强制点，与终点通过 (1) 式更新区间。如果最终区间非空，则该状态的方案数累加到答案中。

复杂度

状态数最多为 $O(n^2)$（每个位置至多两种表达式，区间端点由 $b$ 和 $m$ 的线性组合决定，数目有限）。总转移次数 $O(\text{状态数})$，在 $n\le 2000$ 时可以接受。实际求和 $\sum n \le 5000$，运行时间远小于 $2$ 秒。

答案

输出所有可行方案的总数，对 $998244353$ 取模。

注意事项

• 区间端点可能非常大（$|S|$ 可达 $m\cdot n$，约 $2\times 10^{12}$），使用 long long 或 __int128 存储。
• 初始区间取 $[-10^{18}, 10^{18}]$ 足够覆盖所有可能。
• 当 ? 位置选择 S 时，新强制点位置为 $i-1$，必须保证它大于上一个强制点位置，否则跳过该选择。
• 无需显式存储所有强制点，只需记录最后一个，因为不等式已经保证了前面所有点之间的约束传递性。