4237: Moves on Binary Tree

# Moves on Binary Tree ### 内存 1024MB ### 时间 2S ## 题目描述 有一个完美二叉树，包含 $2^{10^{100}}-1$ 个顶点，编号从 $1,2,...,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 ``` 3 2 URL ``` ### 输出样例1 ``` 6 ``` ### 输入样例2 ``` 4 500000000000000000 RRUU ``` ### 输出样例2 ``` 500000000000000000 ``` ### 输入样例3 ``` 30 123456789 LRULURLURLULULRURRLRULRRRUURRU ``` ### 输出样例3 ``` 126419752371 ``` ## 数据范围与提示 【样例1说明】 完美二叉树的结构如下：  在三次移动中，小高的路径是 $2 \to 1 \to 3 \to 6$。 【样例2说明】 在过程中，小高可能会到达编号超过 $10^{18}$ 的顶点。 【数据范围】 $1 \leq N \leq 10^6, 1 \leq X \leq 10^{18}$，$N$ 和 $X$ 是整数。$S$ 的长度为 $N$，仅由字符 $U$、$L$ 和 $R$ 组成，当小高在根节点时，他不会尝试移动到父节点，当小高在叶节点时，他不会尝试移动到子节点。小高在 $N$ 次移动后所在顶点的编号不超过 $10^{18}$。 ## 题目来源 ABC243D