Electro Master

Luogu

IDLGP9682

Time1000ms

Memory512MB

DifficultyP6

动态规划 DP洛谷原创O2优化组合数学洛谷月赛

考虑一个由四种微观粒子构成的系统：正负 A 子 $\text{a}^+,\text{a}^-$，正负 B 子 $\text{b}^+,\text{b}^-$。一开始，一条直线上放置了 $n$ 个 A 子；然后以某种方式给粒子以初速度，使得带正电荷的粒子向左，反之则向右运动。我们忽略粒子之间的相互作用，认为粒子在加速后速率一定，且均沿直线运动。当两个粒子相撞时，粒子会反弹，沿着相反的方向继续运动。同时满足如下的变换规律： - 若两种粒子的电荷相同，则无事发生； - 若两种粒子的电荷不同，则改变成另一种同电荷的粒子。例如：$\text{a}^-$ 和 $\text{b}^+$ 相撞后，$\text{a}^-$ 会变成 $\text{b}^-$，$\text{b}^+$ 会变成 $\text{a}^+$，并各自沿着相反的方向运动。定义一种摆放方式的权值为，经过足够长的时间后，在左侧收集到的 B 子个数。现在已经确定了一些 A 子的正负性，剩下的 A 子可能带正电，也有可能带负电。请求出对于所有可能方案的权值之和。你需要将答案对 $998\,244\,353$ 取模。 ## Input 输入一行一个长为 $n$ 的字符串 $s$，代表从左到右的 A 子的正负性。具体而言： - 若 $s_i$ 为 `+`，则第 $i$ 个 A 子带正电； - 若 $s_i$ 为 `-`，则第 $i$ 个 A 子带负电； - 若 $s_i$ 为 `?`，则第 $i$ 个 A 子可能带正电，也可能带负电。 ## Output 输出一行一个数，代表答案对 $998\,244\,353$ 取模后的结果。 [samples] ## Background I might be wrong. ## Note #### 样例 1 解释有两种可能的填法：`+++-` 或 `+-+-`。其权值分别为 $0,1$，所以最终的答案即为 $1$。 ### 数据规模与约定对于所有数据，保证 $1\le n\le 2000$，$s_i\in \{\texttt{+},\texttt{-},\texttt{?}\}$。 | # | $n\le $ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | | 0 | - | 样例 | $0$ | | 1 | $100$ | $s$ 中没有 `?` | $10$ | | 2 | $100$ | - | $20$ | | 3 | $300$ | $s$ 中 `?` 不超过 $15$ 个 | $15$ | | 4 | $300$ | - | $20$ | | 5 | - | - | $35$ |

Samples

Input #1

+?+-

Output #1

Input #2

??+-?-+

Output #2

Input #3

-????-?+?--????

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Electro Master",
    "description": {
      "content": "考虑一个由四种微观粒子构成的系统：正负 A 子 $\\text{a}^+,\\text{a}^-$，正负 B 子 $\\text{b}^+,\\text{b}^-$。 一开始，一条直线上放置了 $n$ 个 A 子；然后以某种方式给粒子以初速度，使得带正电荷的粒子向左，反之则向右运动。我们忽略粒子之间的相互作用，认为粒子在加速后速率一定，且均沿直线运动。 当两个粒子相撞时，粒子会反弹，沿着相反的方向继续",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9682"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "考虑一个由四种微观粒子构成的系统：正负 A 子 $\\text{a}^+,\\text{a}^-$，正负 B 子 $\\text{b}^+,\\text{b}^-$。\n\n一开始，一条直线上放置了 $n$ 个 A 子；然后以某种方式给粒子以初速度，使得带正电荷的粒子向左，反之则向右运动。我们忽略粒子之间的相互作用，认为粒子在加速后速率一定，且均沿直线运动。\n\n当两个粒子相撞时，粒子会反弹，沿着相反的方向继续...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments