P6424 [COCI 2008/2009 #2] SETNJA

在二叉树中： - 每个节点都有两个孩子——一个左孩子和一个右孩子。 - 如果节点标记为整数 $x$，则其左子节点标记为 $2x$，右子节点标记为 $2x+1$。 - 树的根标为 $1$。 在二叉树上从根开始遍历。遍历中的每一步要么是跳到左孩子上，要么是跳到右孩子上，或暂停休息（停留在同一节点上）。 用由字符 `L`，`R` 和 `P` 组成的字符串描述遍历过程。 - `L `表示跳到左孩子； - `R `表示跳到右孩子； - `P `表示暂停一轮操作。 $walk$ 的值是我们最终到达的节点的标签。例如，`LR` 的 $walk$ 值为 $5$，而 `RPP` 的 $walk$ 值为 $3$。 一次遍历由 `L`，`R`，`P` 和 `*` 描述。每个 `*` 可以是三个动作中的任何一个。 例如， `L*R` 可能代表 `LLR`，`LRR` 和 `LPR`。集合 `**` 可能代表 `LL`，`LR`，`LP`，`RL`，`RR`，`RP`，`PL`，`PR ` 和 `PP`。 最后，一次遍历后的 $walk$ 的总值是该次遍历中所有可能的遍历顺序的每一步所形成的 $walk$ 的值的总和。 计算给定遍历顺序后的 $walk$ 的总值。

一行一个字符串，表示遍历顺序。

一行一个整数，表示 $walk$ 的总值。

#### 数据规模与约定 - 对于 $30\%$ 的数据，保证输入的字符串中无 `*` 字符。 - 对于 $50\%$ 的数据，保证输入的字符串中至多有三个 `*` 字符。 - 对于 $100\%$ 的数据，保证输入字符串长度小于 $10000$，字符串的每一位只可能是 `L`，`R`，`P`，`*`。 #### 说明 - #### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) SETNJA，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。