时间限制 / 1.0s
空间限制 / 1024MB
题目描述
数轴上有 $n$ 个小球，相邻两个小球的间距相同。每个小球有两种属性：量子 (A) 和虚数 (B)，带有正电荷或者负电荷。一开始所有的小球都是量子 (A) 属性。
通过某种方式给所有的小球初速度，使得带正电荷的小球向左，反之则向右运动。我们认为所有小球的速度相同，且均沿直线运动。
当两个小球到达同一位置时，会发生弹性碰撞，沿着相反的方向按照原有速度继续运动。同时，这两个小球的电性会发生反转，属性也会发生反转。
例如：$\text{A}^-$ 和 $\text{B}^+$ 相撞后，$\text{A}^-$ 会变成 $\text{B}^+$，$\text{B}^+$ 会变成 $\text{A}^-$，并各自沿着相反的方向运动。
定义一种摆放方式的权值为，经过足够长的时间后，在左侧收集到的虚数 (B) 小球个数。
现在已经确定了一些小球的电性，剩下的小球可能带正电，也有可能带负电。请求出对于所有可能方案的权值之和。你需要将答案对 $998244353$ 取模。
输入格式
输入一行一个长为 $n$ 的字符串 $s$，代表从左到右小球的电性。具体而言：
- 若 $s_i$ 为
+，则第 $i$ 个小球带正电； - 若 $s_i$ 为
-，则第 $i$ 个小球带负电； - 若 $s_i$ 为
?，则第 $i$ 个小球可能带正电，也可能带负电。
输出格式
输出一行一个数表示答案。
样例输入输出
- 样例输入 1
+?+-- 样例输出 1
1- 样例输入 2
??+-?-+- 样例输出 2
12- 样例输入 3
-????-?+?--????- 样例输出 3
3675该题还附加了 8 个额外样例，分别对应每个子任务的限制情况。
数据范围
对于 100% 的数据，$1\le n\le 2\times 10^6$。
| 子任务编号 | 分值 | $n\le$ | 特殊性质 |
|---|---|---|---|
| 1 | 10 | $10$ | 无 |
| 2 | 10 | $2\times 10^6$ | $s$ 中没有 ? |
| 3 | 10 | $5\times 10^3$ | $s$ 中 ? 不超过 15 个 |
| 4 | 10 | $40$ | 无 |
| 5 | 10 | $300$ | 无 |
| 6 | 20 | $5\times 10^3$ | 无 |
| 7 | 10 | $2\times 10^5$ | 无 |
| 8 | 20 | $2\times 10^6$ | 无 |
样例解释
在样例一中，如果初始局面是 +++-，最终将会收集到三个量子 (A) 小球，不会造成贡献；如果初始局面是 +-+-，则会收集到一个量子 (A) 和一个虚数 (B) 小球，造成 1 点贡献。所以总的答案是 1。