AT_abc243_d [ABC243D] Moves on Binary Tree

题目描述

有一棵顶点数为 $2^{10^{100}}-1$ 的完全二叉树，每个顶点编号为 $1,2,\ldots,2^{10^{100}}-1$。 顶点 $1$ 是根节点，对于每个 $1 \leq i < 2^{10^{100}}-1$，顶点 $i$ 有左儿子 $2i$，右儿子 $2i+1$。

高桥君最初位于顶点 $X$，接下来进行 $N$ 次移动。移动由字符串 $S$ 给出，第 $i$ 次移动按如下方式进行：

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

请你求出 $N$ 次移动后高桥君所在的顶点编号。保证输入数据使得答案不会超过 $10^{18}$。

输入格式

输入从标准输入读入，格式如下：

$N$ $X$ $S$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 2
URL

输出 #1

6

输入输出样例 #2

输入 #2

4 500000000000000000
RRUU

输出 #2

500000000000000000

输入输出样例 #3

输入 #3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

输出 #3

126419752371

说明/提示

限制条件

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 10^{18}$
• $N, X$ 均为整数
• $S$ 的长度为 $N$，且仅包含 U、L、R
• 当高桥君在根节点时，不会尝试向父节点移动
• 当高桥君在叶节点时，不会尝试向子节点移动
• 高桥君经过 $N$ 次移动后所在的顶点编号不会超过 $10^{18}$

样例解释 1

完全二叉树的结构如下所示。

每次移动后，高桥君所在的顶点编号依次为 $2 \to 1 \to 3 \to 6$。

样例解释 2

在移动过程中，高桥君所在的顶点编号可能会超过 $10^{18}$。

由 ChatGPT 4.1 翻译