#P3612. [USACO17JAN] Secret Cow Code S

[USACO17JAN] Secret Cow Code S

题目描述

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string ss, let F(s)F(s) be ss followed by ss "rotated" one character to the right (in a right rotation, the last character of ss rotates around and becomes the new first character). Given an initial string ss, the cows build their infinite-length code string by repeatedly applying FF; each step therefore doubles the length of the current string.

Given the initial string and an index NN, please help the cows compute the character at the NNth position within the infinite code string.

输入格式

The input consists of a single line containing a string followed by NN. The string consists of at most 30 uppercase characters, and N1018N \leq 10^{18}.

Note that NN may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a "long long" in C/C++).

输出格式

Please output the NNth character of the infinite code built from the initial string. The first character is N=1N=1.

题目大意

题目描述

奶牛们正在实验秘密代码,并设计了一种方法用于生成无限长度的字符串,作为他们代码的一部分。

给定一个字符串 ss,令 F(s)F(s)ss 后接 ss 向右“旋转”一个字符的结果(在右旋转中,ss 的最后一个字符旋转并成为新的第一个字符)。给定初始字符串 ss,奶牛们通过重复应用 FF 来构建他们的无限长度代码字符串;因此每一步都会使当前字符串的长度翻倍。

给定初始字符串和一个索引 NN,请帮助奶牛计算无限代码字符串中第 NN 个位置的字符。

输入格式

输入由一行组成,包含一个字符串和 NN。字符串最多由 30 个大写字母组成,且 N1018N \leq 10^{18}

请注意,NN 可能太大,无法放入标准的 32 位整数中,因此你可能需要使用 64 位整数类型(例如,C/C++ 中的 "long long")。

输出格式

请输出从初始字符串构建的无限代码字符串的第 NN 个字符。第一个字符的位置为 N=1N=1

提示

在这个例子中,初始字符串 COW 按以下方式扩展:

COW -> COWWCO -> COWWCOOCOWWC

COW 8
C

提示

In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC

12345678