← 返回题目列表

AtCoder · joi2020_yo2_e

E. 石头剪刀布表达

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

配点: 100 点

問題文

在这个问题中,剪刀石头布的动作“goo”、“choki”和“pa”分别是 由 \mathrm{R}, \mathrm{S}, \mathrm{P} 代表。\mathrm{R} 是 您也可以写 \mathrm{S} , 赢得\mathrm{S} 是 您也可以写 \mathrm{P} , 赢得\mathrm{P} 是 您也可以写 \mathrm{R} 。 当

x, y 用作石头剪刀布动作时, 定义x + y,\, x - y,\, x \ast y 如下(这些不是通常意义上的加法、减法或乘法):

  • x + y 是x \ne y 什么时候 x 和 按字典顺序比较 y ,以获胜者为准,x = y 什么时候 x 。
  • x - y 是x \ne y 什么时候 x 和 按字典顺序比较 y 中失败的一个,x = y 什么时候 x 。
  • x \ast y 是x \ne y 什么时候 \mathrm{R}, \mathrm{S}, \mathrm{P} 出 x 但是 y 和x = y 什么时候 x 。

石头剪刀布手 由 +, -, \ast 和括号组成的表达式计算如下:

  • 首先计算括号中的项目。例如,\mathrm{R} \ast (\mathrm{P} + \mathrm{S}) = \mathrm{R} \ast \mathrm{S} = \mathrm{P} 。
  • 对于具有相同括号深度的部分, 来自
    • +, - 捻 \ast 优先计算。例如,\mathrm{R} - \mathrm{P} \ast \mathrm{S} = \mathrm{R} - (\mathrm{P} \ast \mathrm{S}) = \mathrm{R} - \mathrm{R} = \mathrm{R} 。
    • 具有相同优先级的(+ 什么?- 什么?+ 和 按字典顺序比较 -,\ast ) 从左开始按顺序计算。例如,\mathrm{R} - \mathrm{P} + \mathrm{S} = (\mathrm{R} - \mathrm{P}) + \mathrm{S} = \mathrm{R} + \mathrm{S} = \mathrm{R} 。

JOI 有一定的石头剪刀布公式,但在该公式中, \mathrm{R}, \mathrm{S}, \mathrm{P} 的一部分不再可见。不再可见的部分 长度表示为 ? 给出了 N 的字符串 E 。 JOI先生看着每一个看不见的部分。 \mathrm{R}, \mathrm{S}, \mathrm{P} 是一种分配以下之一的方法 我想知道有多少种方式可以变成 A 。由于数量可能非常大, 我想求除以1\,000\,000\,007 后的余数。

本题中使用的语法使用 BNF(巴科斯-诺尔表示法)表示如下。石头剪刀布公式中不再可见的部分是<表达式>。

<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "R" | "S" | "P" | "?" | "(" <expression> ")"

例如,说一个字符串是一个<表达式>意味着它是一个<术语>,或者说一个字符串是一个<表达式>,+,<term> 的字符串,按此顺序连接”或“<表达式> 的字符串,-、 <term> 按此顺序连接,依此类推。

一个字符串,即 <表达式> E 和计算结果 给出了 A ,所以? 至 该值是 \mathrm{R}, \mathrm{S}, \mathrm{P} 是一种分配以下之一的方法 A 的数量为 1\,000\,000\,007 后的余数。

制約

  • 1 \leqq N \leqq 200\,000.
  • E 是长度为 N 的字符串。
  • E 是问题陈述中定义的<表达式>。
  • A 是 您也可以写 R 或 至少 S 或 至少 P 。

小課題

  1. (20 点) N \leqq 15.
  2. (20 点) N \leqq 200.
  3. (60 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N
E
A

出力

在标准输出上, 计算所有带有? 至 该值是 \mathrm{R}, \mathrm{S}, \mathrm{P} 是一种分配以下之一的方法 A 的数量为 1\,000\,000\,007 后的余数 1 请按行输出。


入力例 1

11
S+?-(R+?)*P
S

出力例 1

6

2 指定 ? 至 该值是 \mathrm{R}, \mathrm{S}, \mathrm{P} 之一来计算计算结果。 \mathrm{S} 的制作方法如下: 6 有一条街:

  • \mathrm{S} + \mathrm{R} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}
  • \mathrm{S} + \mathrm{R} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}
  • \mathrm{S} + \mathrm{S} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}
  • \mathrm{S} + \mathrm{S} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}
  • \mathrm{S} + \mathrm{P} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}
  • \mathrm{S} + \mathrm{P} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}

入力例 2

15
?+?-?*?+?-?*?+?
R

出力例 2

2187

入力例 3

13
(((((R)))))+?
P

出力例 3

1

入力例 4

1
P
S

出力例 4

0

入力例 5

27
R+((?+S-?*P+?)-P*?+S-?)*R+?
P

出力例 5

381

入力例 6

83
((R+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))-((S+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))
P

出力例 6

460353133

满足条件的分配方法为 10\,460\,353\,203 既然有很多方法, 1\,000\,000\,007 所得的余数 请输出 460\,353\,133 。 你只需要砍掉