← 返回题目列表

AtCoder · arc164_d

D. 一维库仑

中文机器翻译题面 查看原题

分数: 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.