Description
Consider a string A = "12345". An infinite string s is built by performing infinite steps on A recursively. In i-th step, A is concatenated with ‘...$|reverse(A), where | denotes concatenation.
Constraints:1<=Q<=10^5, 1<=POS<=10^12
思路
这个无限的字符串S是什么样子的呢， 12345$54321$$12345$54321.....
12345
12345$54321
12345$54321$$12345$54321
可以发现长度的规律是：L(k) = 2*L(k-1) + (k-1) k是当前的步数，L(1) = 5
从第二步开始，S就是中心对称的，所以可以想到用递归的方法来做这道题，怎么递归：
- 找到最小步数
steps, 使得 S 经过steps后长度L大于n - 如果
n <= 11, 递归结束 - 判断n是不是刚好处于S中间的
$上，返回$，递归结束 - 递归x, x等于减去左边对称字符串和中间
$的长度n-left-steps+1
比如：n = 16
12345$54321$$12345$54321
第一步找到 steps = 3, L = 23，完整的S如上，这时中心$左边的对称字符串长度是11
中间的$范围是 12～13， n不在这个范围，所以递归f(3), 3小于11，直接返回结果3
参考实现（O(logn)）
s = list('12345$54321')
def solve(n):
if n <= 11:
return s[n-1]
L, steps = 5, 1
while L < n:
L = L*2 + steps
steps += 1
left = (L - steps + 1) // 2
if left < n < left+steps:
return '$'
return solve(n-left-steps+1)
