Moves on Binary Tree

题目描述

有一棵完美二叉树，包含 $2^{10^{100}}-1$ 个顶点，编号为 $1,2,...,2^{10^{100}}-1。$
顶点 $1$ 是根。对于每个 1\leq i < 2^{10^{100}-1}，顶点 $i$ 有两个孩子：左孩子是顶点 $2i$，右孩子是顶点 $2i+1$。 Takahashi 从顶点 $X$ 出发，执行 $N$ 步移动，由字符串 $S$ 表示。第 $i$ 步的规则如下。

如果 $S$ 的第 $i$ 个字符是 $U$，则移动到当前顶点的父节点。 如果 $S$ 的第 $i$ 个字符是 $L$，则移动到当前顶点的左孩子。 如果 $S$ 的第 $i$ 个字符是 $R$，则移动到当前顶点的右孩子。

求 Takahashi 在执行完 $N$ 步移动后所在顶点的编号。在给定的测试中，保证答案至多为 $10^{18}$。

输入格式

输入由标准输入给出，格式如下： $N$ $X$ $S$

输出格式

输出答案。

3 2
URL

6

4 500000000000000000
RRUU

500000000000000000

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

126419752371

提示

$1 \leq N \leq 10^6$ $1 \leq X \leq 10^{18}$ $N$ 和 $X$ 是整数。 $S$ 的长度为 $N$，且由 $U$、$L$ 和 $R$ 组成。 当 Takahashi 在根节点时，他不会尝试移动到父节点。 当 Takahashi 在叶子节点时，他不会尝试移动到子节点。 Takahashi 在执行完 $N$ 步移动后所在顶点的编号至多为 $10^{18}$。该完美二叉树具有如下结构。 在三个移动中，Takahashi 的路径是 $2 \to 1 \to 3 \to 6$。
在此过程中，Takahashi 可能会处于编号超过 $10^{18}$ 的顶点。

标签: AtCoder|abc243D

来源

AtCoder|abc243D