AT_arc164_d [ARC164D] 1D Coulomb

对于一个长度为 $2N$，由 $N$ 个 `+` 和 $N$ 个 `-` 组成的字符串 $s$，我们考虑如下问题，并将其答案记作 $p(s)$。 > 在数轴上 $x=1,2,3,\ldots,2N$ 的位置上排列着 $2N$ 个小球，其中 $N$ 个小球带有 $+1$ 的电荷，其余 $N$ 个小球带有 $-1$ 的电荷。小球的电荷排列方式由 $s$ 给出，$s$ 的第 $i$ 个字符为 `+` 时，表示 $x=i$ 处放置一个带 $+1$ 电荷的小球，为 `-` 时，表示 $x=i$ 处放置一个带 $-1$ 电荷的小球。 > > 每个小球会按照以下规则同时开始运动。数轴上数值较小的方向称为左，数值较大的方向称为右。 > > - 对于每个小球，在每一时刻，$F$ 按如下公式计算： > $F = \lbrace$（自身左侧所有小球的电荷总和）$-$（自身右侧所有小球的电荷总和）$\rbrace \times$（自身的电荷） > - 每个小球在每一时刻，如果 $F$ 为正则以每秒 $1$ 的速度向右移动，$F$ 为负则向左移动。 > - 若同一时刻同一坐标上同时存在带 $+1$ 电荷和 $-1$ 电荷的小球，则两者相互抵消并消失。 > > 此时，所有小球从开始运动到消失为止所移动距离（消失位置与初始位置的绝对值之差）的总和是多少？ 给定一个长度为 $2N$，由 `+`、`-`、`?` 组成的字符串 $T$。将 $T$ 中的 `?` 替换为 `+` 或 `-`，使得最终得到的字符串 $s$ 恰好有 $N$ 个 `+` 和 $N$ 个 `-`。对于所有可能的 $s$，求 $\sum p(s)$，并对 $998244353$ 取模。 在给定的约束和运动规则下，可以保证所有小球在有限时间内全部消失，且只要小球未消失，其 $F$ 的值不会为 $0$，不会出现三球及以上同时位于同一坐标的情况，且 $p(s)$ 一定为整数。

输入通过标准输入给出。 > $N$ $T$

输出 $\sum p(s)$ 对 $998244353$ 取模的结果。

## 约束 - $1\leq N\leq 3000$ - $N$ 为整数 - $|T|=2N$ - $T$ 的每个字符为 `+`、`-` 或 `?`，且 `+` 和 `-` 的数量均不超过 $N$ ## 样例解释 1 从 $T$ 可以得到的字符串 $s$ 有 `++--` 和 `+-+-`。对于 `++--`，开始运动时每个小球左右的电荷总和及 $F$ 的值如下图所示。  因此，$x=1,2$ 的小球向右，$x=3,4$ 的小球向左运动。在这种情况下，每个小球之后都不会改变运动方向，$x=2,3$ 的小球将在 $0.5$ 秒后于 $x=2.5$ 相遇消失，$x=1,4$ 的小球将在 $1.5$ 秒后于 $x=2.5$ 相遇消失。在此期间，$x=2,3$ 的小球各自移动 $0.5$，$x=1,4$ 的小球各自移动 $1.5$，因此 $p(\texttt{++--})=4$。同理可得 $p(\texttt{+-+-})=2$，所以所求 $p(s)$ 的总和为 $6$。 ## 样例解释 2 请输出 $p(s)$ 的总和对 $998244353$ 取模的结果。 由 ChatGPT 4.1 翻译