Secret Cow Code

题目描述

奶牛们正在尝试秘密代码，并设计了一种方法来生成一个无限长度的字符串，用作其代码的一部分。 给定一个字符串 $s$，令 $F(s)$ 为 $s$ 后接将 $s$ 向右“旋转”一个字符后的结果（在一次右旋中，$s$ 的最后一个字符会旋转到最前面，成为新的第一个字符）。给定一个初始字符串 $s$，奶牛们通过反复应用 $F$ 来构建它们的无限长度代码字符串；因此每一步都会将当前字符串的长度加倍。 给定初始字符串和一个下标 $N$，请帮助奶牛计算该无限代码字符串中第 $N$ 个位置的字符。

输入格式

输入由一行组成，包含一个字符串以及 $N$。 该字符串由不超过 30 个大写字母组成，并且 $N \leq 10^{18}$。 注意 $N$ 可能大到无法装入标准 32 位整数，因此你可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

输出格式

请输出由初始字符串构建出的无限代码字符串中的第 $N$ 个字符。第一个字符对应 $N=1$。

COW 8

C

提示

在这个例子中，初始字符串 COW 的扩展过程如下： COW -> COWWCO -> COWWCOOCOWWC 12345678 题目来源：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver