分数: 600 点
问题陈述
考虑以下字符串问题 s 长度 2N 由以下人员组成 N + 和 N -,让 p(s) 表示答案。
有 2N 球在位置上排列 x=1,2,3,\ldots , 2N 在数轴上,其中 N 收费 +1 以及剩余的 N 收费 -1。球的电荷排列由下式表示 s。如果 i- 第一个字符 s is
+,一个电荷为 +1 位于 x=i;如果是的话-,一个电荷为 -1 位于 x=i.每个球根据以下规则同时开始运动。这里,我们将数轴上较小数所在的方向称为“左”,将较大数所在的方向称为“右”。
- 对于每个球,定义 F 在每个时刻由以下公式计算:
F=\lbrace (严格位于其左侧的球的电荷总和) - (严格位于其右侧的球的电荷总和) \rbrace \times (自身的电荷).- 在每个时刻,每个球都会向右移动,如果 F 为正,如果 F 为负,速度为 1 每秒。
- 如果球的电荷为 +1 和一个带电荷的球 -1 同时存在于同一坐标处,它们相互抵消并消失。
那么,小球开始运动到消失之前移动的距离之和是多少(小球移动的距离是它开始运动和消失的坐标的绝对差)?
给你一个字符串 T 长度 2N 组成 +, -,和 ?。求总和 p(s) 所有字符串 s 由以下人员组成 N + 和 N - 可以通过替换每个来获得 ? in T 与 + or -,模数 998244353.
在给定的约束和运动规则下,可以证明所有球在有限时间内消失,即 F 每个球不会变成 0 直到该球消失,不存在三个或更多球同时处于同一坐标的时刻,并且 p(s) 是一个整数。
约束
- 1\leq N\leq 3000
- N 是一个整数。
- |T|=2N
- 每个字符 T 是
+,-,或?,最多有 N+最多 N-.
输入
输入由标准输入按以下格式给出:
N T
输出
打印答案模数 998244353,作为整数。
示例输入 1
2 +??-
示例输出 1
6
字符串 s 可以从 T 是 ++-- 和 +-+-.
对于 ++--,每个球左右两侧的球的电荷总和,以及
议案开始时的 F 如下:

因此,球在 x=1,2 开始向右移动,球在 x=3,4 开始向左移动。
然后,每个球继续沿同一方向移动,而不改变其运动方向,并且从 x=2,3 消失于 x=2.5 之后 0.5 秒,以及开始于 x=1,4 消失于 x=2.5 之后 1.5 秒。
在这些时间里,开始于 x=2,3 移动距离 0.5 每个,以及开始于 x=1,4 移动距离 1.5 每个,所以 p( ++-- )=4.
同样可以看出 p( +-+- )=2,所以求和 p(s) is 6.
示例输入 2
17 ??????????????????????????????????
示例输出 2
285212526
请务必打印 p(s) 模数 998244353.