Score : $400$ points

问题描述

存在一棵完全二叉树，拥有 $2^{10^{100}}-1$ 个顶点，编号分别为 $1,2,...,2^{10^{100}}-1$。
顶点 $1$ 是根节点。对于每个 $1\leq i < 2^{10^{100}-1}$，顶点 $i$ 拥有两个子节点：左边为顶点 $2i$，右边为顶点 $2i+1$。

高桥从顶点 $X$ 出发，并执行由字符串 $S$ 表示的 $N$ 步操作。第 $i$ 步操作如下：

• 若 $S$ 的第 $i$ 个字符是 U，则前往当前所在顶点的父节点。
• 若 $S$ 的第 $i$ 个字符是 L，则前往当前所在顶点的左子节点。
• 若 $S$ 的第 $i$ 个字符是 R，则前往当前所在顶点的右子节点。

请计算高桥在执行完 $N$ 步操作后所在的顶点的编号。在给定的情况下，保证答案不超过 $10^{18}$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a perfect binary tree with $2^{10^{100}}-1$ vertices, numbered $1,2,...,2^{10^{100}}-1$.
Vertex $1$ is the root. For each $1\leq i < 2^{10^{100}-1}$, Vertex $i$ has two children: Vertex $2i$ to the left and Vertex $2i+1$ to the right.

Takahashi starts at Vertex $X$ and performs $N$ moves, represented by a string $S$. The $i$-th move is as follows.

• If the $i$-th character of $S$ is U, go to the parent of the vertex he is on now.
• If the $i$-th character of $S$ is L, go to the left child of the vertex he is on now.
• If the $i$-th character of $S$ is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after $N$ moves. In the given cases, it is guaranteed that the answer is at most $10^{18}$.

Constraints

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 10^{18}$
• $N$ and $X$ are integers.
• $S$ has a length of $N$ and consists of U, L, and R.
• When Takahashi is at the root, he never attempts to go to the parent.
• When Takahashi is at a leaf, he never attempts to go to a child.
• The index of the vertex Takahashi is on after $N$ moves is at most $10^{18}$.

Input

Input is given from Standard Input in the following format:

$N$ $X$

$S$

Output

Print the answer.

Sample Input 1

3 2
URL

Sample Output 1

6

The perfect binary tree has the following structure.

In the three moves, Takahashi goes $2 \to 1 \to 3 \to 6$.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds $10^{18}$.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

update @ 2024/3/10 10:27:24